{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "BIOINFORMATICSORIGINALPAPERVol.21no.112005,pages2748–2758doi:10.1093/bioinformatics/bti338DataandtextminingMaSTerClass:acase-basedreasoningsystemfortheclassiﬁcationofbiomedicaltermsIrenaSpasic1,∗,SophiaAnaniadou2andJunichiTsujii31SchoolofChemistry,TheUniversityofManchester,SackvilleStreet,POBox88,ManchesterM601QD,UK,2SchoolofComputing,ScienceandEngineering,TheUniversityofSalford,TheCrescent,SalfordM54WT,UKand3FacultyofInformationScienceandTechnology,TheUniversityofTokyo,7-3-1Hongo,Bunkyo-ku,Tokyo113-0033,JapanReceivedonNovember19,2004;revisedonFebruary13,2005;acceptedonFebruary17,2005AdvanceAccesspublicationFebruary22,2005ABSTRACTMotivation:Thesheervolumeoftextuallydescribedbiomedicalknowledgeexertstheneedfornaturallanguageprocessing(NLP)applicationsinordertoallowﬂexibleandefﬁcientaccesstorelev-antinformation.Specializedsemanticnetworks(suchasbiomed-icalontologies,terminologiesorsemanticlexicons)cansigniﬁcantlyenhancetheseapplicationsbysupplyingthenecessaryterminologicalinformationinamachine-readableform.Withtheexplosivegrowthofbio-literature,newterms(representingnewlyidentiﬁedconceptsorvariationsoftheexistingterms)maynotbeexplicitlydescribedwithinthenetworkandhencecannotbefullyexploitedbyNLPapplic-ations.Linguisticandstatisticalcluescanbeusedtoextractmanynewtermsfromfreetext.Theextractedtermsstillneedtobecor-rectlypositionedrelativetoothertermsinthenetwork.Classiﬁcationasameansofsemantictypingrepresentstheﬁrststepinupdatingasemanticnetworkwithnewterms.Results:TheMaSTerClasssystemimplementsthecase-basedreas-oningmethodologyfortheclassiﬁcationofbiomedicalterms.Availability:MaSTerClassisavailableathttp://www.cbr-masterclass.org.Itisdistributedunderanopensourcelicenceforeducationalandresearchpurposes.ThesoftwarerequiresJava,JWDSP,Ant,MySQLandX-hivetobeinstalledandlicencesobtainedseparatelywhereneeded.Contact:i.spasic@manchester.ac.ukSupplementaryinformation:Availableathttp://www.cbr-masterclass.org1INTRODUCTIONAterminologyisacollectionofterms(denotingdomain-speciﬁcconceptssuchasgenes,proteins,etc.)typicallyorganizedintoaclassiﬁcationhierarchy.Thecoreofsuchahierarchyisbasedonthegeneral–speciﬁcrelation.Otherrelations(e.g.biochemicalinterac-tions)areusedtocompletethemodelofaspeciﬁcdomain.Conceptsarenativelyassortedintogroups,eitherclasses(whereallconceptsshareacommondescription)orclusters(groupsofcorrelatedcon-cepts),andtheorganizationoftermsinaterminologyneedstoreﬂectsuchpropertiesconsistently.Itshouldalsobeextensiblesothatnewterms,representingnewlydiscoveredconcepts,canbeefﬁcientlyincorporatedintotheexistingstructuresbyassociatingthemwith∗Towhomcorrespondenceshouldbeaddressed.otherterms.Theseassociationsshouldatleastincludethelinksbetweenthecorrelatedterms,thusformingtheclustersofsemantic-allyrelatedterms,andthegeneralizationoftermssharingthesamesetoffeaturesintoappropriateclasses.Givenacorpusofrelevanttextualdocuments,thetechniquesforautomatictermrecognition,clusteringandclassiﬁcation,canhelptoautomatetheprocessofcreatingandmaintainingaspeciﬁctermino-logy.Theneedforautomationisparticularlyevidentinbiomedicine,wheremanualapproachescannotcopewithanenormousandevergrowingnumberoftermsandthecomplexstructureofbiomedicalterminologies.1Inthispaperwedescribeanapproachtoclassiﬁcationofbiomed-icalterms,whoseresultscansupportautomaticterminologyupdate.Structuredup-to-dateterminologicalinformationcanthenbeusedtoimprovethequalityofnaturallanguageprocessingapplications(suchasinformationextractionandretrieval,documentclassiﬁca-tionandsummarization,etc.),thusmakingiteasierforbiomedicalexpertstonavigatethroughhugevolumesofscientiﬁcdocuments.2Automaticclassiﬁcationofbiomedicaltermsisdifﬁcultduetoloosenamingconventions,whichrarelyaimtoencodeparticularfunctionalpropertiesoftheunderlyingconceptsinasystematicmanner.3Forthecomplexityreasonscausedbyinconsistentandimprecisenamingpractice,manymethodsdevelopedforclassiﬁca-tionofbiomedicaltermstargetonlyalimitednumberofspeciﬁcclassesthroughmanualidentiﬁcationoffeaturestypicaloftheirterms.Forexample,Fukudaetal.(1998)developedarule-basedmethodfortherecognitionofproteinnamesexploringtheirortho-graphicandlexicalfeatures(e.g.capitalletters,digitsandspecialcharacters).Aseriesofmethodshavebeenimplementedfollowingthisidea.Forinstance,Narayanaswamyetal.(2003)extended1UMLS(http://www.nlm.nih.gov/research/umls)containsoveronemillionconceptsnamedby5millionterms,organizedintoahierarchyof135classesandinterconnectedby54differentrelations.2Medline(http://www.ncbi.nlm.nih.gov/PubMed)refersto∼12millionjournalarticles,expandingformorethan10000referencesweekly.Over571000referenceswereaddedin2004.3Thereisnoexactconsensusonwhatconstitutesabiomedicaltermevenwhenitisrestrictedto,e.g.proteinsandgenes(Narayanaswamyetal.,2003),althoughthenamingconventionsdoexistfortheseconcepts(Oliveretal.,2002).2748©TheAuthor2005.PublishedbyOxfordUniversityPress.Allrightsreserved.ForPermissions,pleaseemail:journals.permissions@oupjournals.orgDownloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "MaSTerClassFukuda’sapproachtosixclassesofbiomedicalentities:geneorpro-tein,geneorproteinpart,chemical,chemicalpart,sourceandothers.Themainprobleminsuchapproachesisthattermclassiﬁcationrulesareoftenobscureandimpreciseduetoloosenamingconventions.Inordertocopeefﬁcientlywiththecomplexityofknowledgeneededtoperformreliableclassiﬁcation,manyapproachesresorttomachinelearning(ML)techniquestodetectfeaturesthatchar-acterizespeciﬁcclasses.Currently,theMLtermclassiﬁcationmethodsexploitlittleornobiomedicalknowledgeforguidedlearn-ing.Usually,general-purposeMLalgorithmsareappliedtoshallowrepresentationoftext(Nedellec,2002).Forinstance,Stapleyetal.(2002)usedasupportvectormachine(SVM)approachwithanon-structuredrepresentationoftexttoclassifygenenames(rep-resentedasvectorsofcontextualfeatures,deﬁnedassinglewordsco-occurringinthesameabstract)withrespecttotheirsubcellularlocation.Recently,therehavebeenanumberofotherapplicationsofSVMsforclassiﬁcationofbiomedicalterms(Kazamaetal.,2002;Leeetal.,2004;CollierandTakeuchi,2004).Theseapproachesdif-ferfromthoseofStapleyetal.(2002)withrespecttothefeaturesusedwhichlargelyresemblethoseproposedbyFukudaetal.(1998).Alternatively,probabilisticmethodssuchasnaiveBayesclassiﬁca-tion(Hatzivassiloglouetal.,2001;Nobataetal.,2000)andhiddenMarkovmodels(Collieretal.,2001)havebeenused.Allmentionedmethodsrequirelargeamountsoftrainingdataandsigniﬁcanttrainingtimetopreventoverﬁtting.Namely,theyareoptimizedtoﬁtthetrainingdata,whichmaynotbeidealapprox-imationoftherealdata.Thus,suchalgorithmsrequirelargetrainingsetsandneedtobeperiodicallyretrainedupontheadventofnewdata.Theyalsounderperformforminorityclassesduetothedatasparsityproblem.Furthermore,theyexplicitlydifferentiatebetweenthetrain-ingphase(inwhichclassiﬁcationrulesarelearnt)andtheapplicationphase(inwhichthelearntrulesareapplied).However,satisfact-oryrulescannotalwaysbeproduced(e.g.duetoweakcorrelationbetweentermfeaturesandtheirclasses).InthispaperwesuggestanalternativeMLapproach.Case-basedreasoning(CBR)isparticularlysuitablefortheproblemoftermclas-siﬁcationinbiomedicine,becauseitispragmaticandrobustenoughtodealwiththecomplexityofbothnaturallanguageandthebiomed-icaldomainasexplainedinthefollowingsectionwhichoutlinesthebasicprinciplesofthismethodology.2METHODOLOGYCBRisbasedonrememberingspeciﬁcexperiencesthatmaybeusefulfortheproblem(case)beingsolved.Itmaybeviewedasamultistagecycleinvolvingthefour‘re-’(Aamodt,1995):(1)retrievethemostsimilarcase,(2)reusethecasetosolvethenewproblem,(3)revisethesuggestedsolutionand(4)retaintheusefulinformationobtainedduringproblemsolving.Therefore,newprob-lemsaresolvedbyadaptingsolutionsthatprovidedsatisfactoryresultsforsimilarproblems,thusavoidingtheneedforanexplicitmodeloftheproblemdomain(WatsonandMarir,1994).Instead,onlyfeaturesrelevantinthecon-textofthecurrentproblemneedtobeidentiﬁed.Therefore,CBRmakesuseofspeciﬁc(asopposedtogeneralized)knowledgeinbothproblemsolvingandlearning(Kolodner,1993).Speciﬁcinformationaboutthepastexperi-encesisregardedasknowledge,unlikeinrule-basedormodel-basedsystems,whereitistreatedasdata.Inthismanner,CBRtacklesthemainissuesinotherMLsystems,suchasthelackofrobustnessandﬂexibility,conﬁne-menttonarrowproblemdomainsanddifﬁcultdevelopmentandmaintenance(Aamodt,1995).MemoryformsabasisforthelearningabilityofCBRsystems(WatsonandMarir,1994).Nevertheless,suchatrivialformoflearningstillsupportsgeneralizationandabstractionimplicitlythroughtheuseofsimilarity(Aamodt,1995).Therefore,aCBRsystemiscapableoflearningwithoutexplicitlygeneralizingspeciﬁccasesintoformulas,rulesorothersymbolicrepresentations(Globigetal.,1997).Suchalazyordemand-drivenapproachhasthefollowingadvantages(Aha,1998;Leake,1996):easierknowledgeacquisition,reducedproblemsolvingpredisposition,incrementallearningandimproveduseracceptanceduetoexplanationbasedonprecedents.ThegeneraladvantagesofCBRareparticularlyemphasizedinthefamilyofbiomedicalsciencesbecauseofthehomologousnatureofbiologicalsys-temsrootedinevolution(JurisicaandGlasgow,2004).Therefore,biomedicalexpertsthemselvesoftenuseanalogicalreasoningtoplanandconductexper-imentsexploringsimilaritiesbetweennewandknownsystems.Furthermore,biomedicalﬁeldisoverwhelmedbydatabutoftenlacksexactandcompletetheoriesthatcouldinterpretsuchamountsofdatacorrectlyandefﬁciently.Forexample,duetohugeamountsofdata,manyunknowns,incompletetheoriesandextremelydynamicnatureofmolecularbiology,reasoninginthisdomainisoftenbasedonexperienceasopposedtogeneralknowledge.CBRhasbeensuccessfullyappliedinmolecularbiologytosolveavarietyofproblems,e.g.proteincrystallization,genomicsequenceanalysis,proteinstructuredetermination,etc.Similarly,Schmidtetal.(2001)emphasizetheappropriatenessofCBRformedicaldomainusinganargumentthattheknowledgeofmedicalexpertsis‘amixtureoftextbookknowledgeandexperience’.Thetextbookknow-ledgecanberepresentedbyrulesorothermodels,whiletheexperiencecanberepresentedbycases.Moreover,medicalcasesareprofessionallydocu-mentedresultinginaninvaluablerepositoryofinformation,whereCBRcanbeusedas‘anengineforintelligenttextprocessingandretrieval,dataminingandprojectivereasoning’inordertofullyexploitavailableinformationespe-ciallyintheageofelectronicpatientrecords(MacuraandMacura,1997).Furthermore,thetypicaldecisionmakingprocessofamedicalpractitionerinvolvesreasoningwithcases,whichestablishesmedicineasaninteractionofresearchandpractice,whereclinicalpracticeischaracterizedbyacollec-tionofaccumulatedcases.CBRanditslearningstrategymirrorthelearningprocessofamedicalpractitionerwhenfacedwithdifferentcases(patients,symptoms,diseasesandtreatments).Hence,cognitiveadequatenessandexplicitrepresentationofexperiencemakeCBRanaturalMLapproachinmedicine(Gierletal.,1998).Thisfacthasbeenrestatedbynumerousmedicalapplicationsincludingdiagnosis,classiﬁcation,planning,prognosis,tutoring,etc.Inviewofourspeciﬁcproblemofclassifyingbiomedicalterms,CBRcanreadilyutilizethelargebodyofbiomedicaltextsasthetrainingdatawithouttheneedtomaptermfeaturestothecorrespondingclasses,apriori.Instead,generalization(orlearning)isperformedondemandbasedonthecurrentlyavailabledataandwithrespecttoaparticulartermbeingclassiﬁed.Thishelpstoreduceoverﬁtting,whichinotherMLapproachesstemsfromanattempttogeneralizeinadvancesoastoﬁtmostoftheavailabletrainingdata.Moreover,byautomaticallyadaptingtothedataavailableatthemomentofclassiﬁcationandnottraining,theneedforretrainingisavoidedinCBR.Thesepropertiesparticularlysuitthedynamicnatureofthebiomedicaldomain(newdatabecomeavailabledaily)andthedifﬁcultyingeneralizingtermpropertiesintocorrespondingclasses(duetoloosenamingconventionsandthevariabilityofnaturallanguages).HavingchosenCBRasamethodologyforclassiﬁcationofbiomedicalterms,thenextstepistodecidehowtoutilizeitforthisproblem.First,notethatthereisalargeamountofelectronicallyavailablebiomedicaldocumentsdescribingspeciﬁcdiscoveriesandanumberofknowledgerepos-itoriesdescribinggeneralbiomedicalknowledge.Thebiomedicalknowledgerepositories,althoughtypicallyincomplete,stillcontainlargevolumesofinformationinastructuredform.Ontheotherside,scientiﬁcdocumentscontaincomprehensiveup-to-dateinformationstructuredbythenaturallan-guagerules.Ourintentionwastouseacorpusofbiomedicaltexts(inwhichknowntermsareclassiﬁedwithinabiomedicalontology)asacollectionofclassiﬁcationexperiencesandperformclassiﬁcationofnewtermsbymakinganalogiesontheﬂy.Theroleofanontologyinthiscontextistoprovideaclassiﬁcationscheme,aidsemanticinterpretationofdomain-speciﬁctextand2749Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "I.Spasicetal.   general knowledgelinguisticknowledgedomain-specificknowledgeannotated corpuscase-baseterm (---)+contextterm (class)+contextterm (class)+contextterm (class)+contextterm (class)+contextunclassifiedtermoccurrenceretrievalsimilaritymatchingvotingnew caseretrievedcasessimilarcasesmatchedcasesclassifiedcaseFig.1.TheMaSTerClasssystemorganization.supportthesemanticaspectofthesimilaritymeasureusedtoidentifytermcontextssimilartotheoneusedfortheclassiﬁcationofanewterm.3THEMaSTerClassSYSTEMInthissection,weintroducetheMaSTerClass(machinesupportedtermclassiﬁcation)system.AlthoughCBRservedasthemethodo-logicalframework,theactualtechniquesneededtobedevelopedspeciﬁcallyforthegivenproblem.Figure1depictstheorganiz-ationandtheworkﬂowofMaSTerClass.Twotypesofgeneralknowledge(linguisticanddomain-speciﬁc)areutilized.Thelin-guisticknowledgeisusedtostructuretextualinformation,i.e.toextracttheunderlyingsyntacticstructureandrepresentitexplicitlyinamachine-usableform.Acorpusofbiomedicalabstractswasautomaticallyannotatedwithlexical,syntacticandterminologicalinformation.Therulesforrecognizingsyntacticstructuresofinterest(e.g.nounandverbphrases)havebeenspeciﬁedbythecorrespond-inglocalgrammars(Gross,1997).TermshavebeenidentiﬁedinthecorpusbylookinguptheUMLS4dictionaryandapplyingtheNC-value5method.Thedomain-speciﬁcknowledgeadoptedfromUMLSconsistsoftermsandthecorrespondingconcepts(i.e.conceptidentiﬁers)organizedintoaclassiﬁcationhierarchy.4UMLSisanontology,whichmergesover100biomedicalvocabulariesaim-ingtofacilitatethedevelopmentofinformationsystemsfortextprocessinginbiomedicinebyprovidingaformalrepresentationofdomain-speciﬁcknow-ledgeinordertoprocess,retrieve,integrate,andaggregatebiomedicaldataandinformationcontainedintherelevantliterature.5TheNC-value(FrantziandAnaniadou,1999)methodextractsmultiwordterms[>85%oftermsaremultiword(NakagawaandMori,2003)]byusinglinguisticknowledgetoproposetermcandidatesthroughtheirform-ationpatternsfollowedbyfrequency-basedanalysisusedtoestimatetheir‘termhood’.NotethatthefunctionalityoftheMaSTerClasssystemcoverstermclassiﬁcationonly.WhilewecurrentlyuseUMLSandtheNC-valuemethodtoannotatethecorpusterminologically,theyareexternaltothesystemandbynomeanspartofit.Thesameremarkappliestotheuseofotherlinguistictools,suchastaggerandparser.Inotherwords,anyothertagger,parserortermrecognitionmethodcanbeusedjustaswellwithouttheneedforreimplement-ation.Similarly,anyotherontologycouldgenerallybeconvertedintoourinternalformatandstoredintothedatabaseusedbythesystem.TheannotatedcorpusofbiomedicalabstractsusedincombinationwiththeUMLSontologyformsthecase-baseoftheMaSTerClasssystem.Itisusedfortermclassiﬁcationbyrememberingspeciﬁcclassiﬁcationcontextsthatcanbeusefulforthetermcurrentlybeingclassiﬁed.Newtermsareclassiﬁedbyadapting(ormoreprecisely,adopting)theclassesofsimilartermsinsimilarcontexts.Eachcaseinthisapproachconsistsofatermoccurringinaspeciﬁccontext(descriptionoftheproblem)andoneormoreclassesthatapplytothattermoccurrence(solution).Itwouldnotbeefﬁcient(orevenfeasible)tocompareanewtermtoallavailabletermsandtheircontexts.Forthisreason,onlypotentiallysimilarcontextsareretrievedbyusingterminologicalinformationfromtheontologytolocateothercontextscontainingsemanticallysimilartermsanddomain-speciﬁcverbs.ThenewcaseiscomparedwitheachretrievedcasebytheSOLD(syntactic,ontology-drivenandlexicaldistance)measure,whichcomparestheirsyntacticandsemanticproperties.Itisbasedontheconceptoftheeditdistance(ED),whichhasbeenwidelyusedforapproximatestringmatch-ing(Navarro,2001).Itcomparestwostringsthroughtheminimalnumber(orcost)ofeditoperations(includingdeletion/insertionofacharacterandthereplacementoftwocharactersinthetwostrings).TheSOLDmeasureusesthesameoperations,butappliesthemtosyntacticelements(obtainedthroughlexicaltaggingandpartialsyntacticparsing)andterms(obtainedautomaticallybytheNC-valuemethodordictionarylook-up).Bothlinguisticandter-minologicalknowledgeareusedtoapproximatelymatchindividualcontextelements.Themostsimilarretrievedcasesareselectedforfurtherpro-cessing.Theselectionprocess,thus,furtherreducesthesearchspacetobeprocessedinthematchingphase,inwhichthenewcaseandoldcasesarealignedaccordingtothecombinationsofeditoperationsresultingintheminimalalignmentcost.Thepur-poseofalignmentistomatchtheunclassiﬁedtermtoaclassiﬁedtermthathasasimilarroleinasimilarcontext(bothsyntacticallyandsemantically).Thesuccessfullymatchedcasesareusedcollect-ivelytoproposetheclass(es)fortheunclassiﬁedtermthroughavotingprocedure.Eachcasecontributestotheﬁnalclassiﬁcationresultsbydelegatingvotesfortheclassesattachedtothematchedclassiﬁedterm.Forexample,inFigure2letussupposethattheunclassiﬁedterm5alpha-dihydrotestosteroneisalignedwiththetermtestosteroneclassiﬁedashormone.Thentheclasssuggestedfor5alpha-dihydrotestosteronebythisalignmentishormoneaswell.Asmultiplecasesareused,itisexpectedthatanyoutlyingcasesthatgotthroughretrieval,selectionandmatchingwouldbeoutvotedatthisstage.Finally,theclassesreceivingmostvotesaresuggestedforthegivenunclassiﬁedterm.Followingavalidationpro-cedureperformedbyahumancurator,thenewlylearntcase(i.e.thetermsuccessfullyclassiﬁedbasedonitscontext)canbeaddedtothecase-base.2750Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "MaSTerClasstestosterone but not progesterone inhibits [3H]R1881 binding to AR --- ------- 5 alpha-dihydrotestosterone ---- ---- ---------------- inhibited [3H]R1881 binding to the androgen receptor in kidney Fig.2.Analignmentofsimilarcontexts.4MODULESIntheprevioussectionwedescribedthegeneralworkﬂowoftheMaSTerClasssystem.Hereweprovidemoredetailsaboutitsmodules.4.1Case-baseAcaseisaunitencapsulatingknowledgerelevanttoaparticularexperience(WatsonandMarir,1994).Itistypicallystructuredintotheproblemandsolutionparts.Casesmayberepresentedasfeaturevectors,frames,objects,predicates,semanticnets,rules,etc.Thecaserepresentationaffectsthewayinwhichthesimilaritybetweencasescanbeassessedandtheefﬁciencyofretrieval.InMaSTerClass,theproblemisatermoccurrencefoundintext,whilethesolutionrepresentsasetofclassesapplicabletothegiventerm.Asthecontextinwhichatermoccursisoftennecessaryforitsclassiﬁcation,6wecanviewtheproblempartasatermwithinagivencontext.Thenextquestionishowthecontextshouldberepresented,e.g.bagofco-occurringwordsorterms,textwindowofaﬁxedlength,sentence,paragraphordocumentcontainingtheterm,lexico-syntacticpatternmatchingthecontext,etc.Inourapproach,wekeptasmuchcontex-tualinformationaspossible.First,eachcontexthasbeenannotatedwithlexical,syntacticandterminologicalinformationandtreatedasasequenceofsyntacticandterminologicalunits.Basicsyntacticstructures(e.g.nounandverbphrases)arerecognizedthroughpar-tialparsing.DictionarytermsareannotatedtogetherwiththeonesrecognizedbytheNC-valuemethod.Bothtermsandbasicsyntacticstructuresaremostoftenmultiwordunits.Bygroupingandannot-atingthesemultiwordunitsthecontextisstructured,i.e.functionalrelationsbetweenconsecutivesinglewordsarepreserved.Inaddi-tion,thepositionalinformationforindividualcontextelementsisretained.Second,therelationofalocalcontextandtheglobaldis-courseispreservedbydecidingtouseapointertoatermoccurrenceinthecorpusratherthanacopyofitscontext.Itisaﬂexibleapproach,becausethestructureandlengthofacontextneednotbeprespeciﬁed.Atermisclassiﬁedbymappingittoitsclassandlinkingittotheknowledgeonthatclassrepresentedbytheontology.Thus,thesolutiontotheproblemofclassifyingatermisapartoftheontologyconcernedwiththatparticularterm.4.2SimilaritymeasureCBRreliesonthehypothesisthatsimilarproblemstendtohavesimilarsolutions.Therefore,thesimilarityassessmentisakeyissueinCBR.Itdependsonaproblemdomainandcaserepresentation.Inthechosenrepresentation,eachcasecorrespondstoatermcontexttreatedasasequenceofbasicsyntacticstructuresandweneedtoapproximatelymatchsuchsequences.EDhasbeenwidelyusedforapproximatestringmatching,wherethedistancebetweenidenticalstringsequalszeroandincreasesasthestringsgetmoredissimilar6Whenclassifyingbiomedicalterms,itisbyallmeansnecessarytoincludetheircontextintoconsiderationsince(1)termsdonotnecessarilyencodesufﬁcientinformationtoinfertheirsemantictypesand(2)themeaningofatermcanbemodiﬁedbyitscontext.withrespecttothesymbolstheycontainandtheorderinwhichtheyappear.EDisdeﬁnedastheminimalcostincurredbythechangesneededtotransformonestringintotheother.Thesechangesmayincludeinsertionordeletionofasinglecharacter,replacementoftwocharactersinthetwostringsandtranspositionoftwoadjacentcharactersinasinglestring.Thechoiceofeditoperationsandtheircostsdependsonaspeciﬁcapplication.EDhasbeensuccessfullyutilizedinNLPtodealwithalternatespellings,misspellings,theuseofupper-andlower-caseletters,etc.Ithasalsobeenusedinterminologicalprocessingfortherecognitionoforthographictermvariants.Forexample,TsuruokaandTsujii(2004)comparedproteinnamesbasedontheirinternalpropertiesfocusingonorthographicfeatures.Ourintention,however,isprimarilytoexplorecontextualpropertiesofterms.Inthiscase,itismoreconvenienttoapplyEDatthewordlevelratherthanthecharacterlevel,i.e.thecharacter-basedEDdoesnotcopewellwithpermutationsofwords.Forinstance,judgingbythe‘conventional’ED,stoneinkidneyismoresimilartostoneinbladderthankidneystone.Alternatively,approximatestringmatchingcanbeviewedastheproblemofpairinguptheirwordssoastominimizetheirED(Frenchetal.,1997).Recently,EDhasbeenappliedatthewordleveltoallowdifferentwordingsandsyntacticmistakesinthephrase-basedtextsearch(Navarroetal.,2000).Inthisapproach,EDwassimplyappliedtowordsasopposedtocharacters.We,however,developedtheSOLDmeasurebyenrichingthebasicEDapproachwithbothlinguistic[relyingonpart-of-speech(POS)taggingandpartialparsing]andbiomedical(usinganontology)knowledge(SpasicandAnaniadou,2005).7PartialparsingisappliedtoPOS-taggedtexttogroupsubsequentwordsintobasicsyntacticstructures.EDappliedtoblocksofwordsratherthanindividualwordsis‘forced’totakesyntacticstructure(atthephraselevel)intoaccountandpreventedfromartiﬁciallydis-assemblingsyntagmaticstructuresbyapplyingeditoperationstoindividualwords.Bychoosingtoreplacesyntacticcategorieswithsimilarpropertiesatlowercosts(e.g.nounsandpronouns),EDcanalsobeusedtocomparethesyntacticstructureatthesentencelevel,i.e.thesentencesreceivinglowEDvaluesaretheonesthatcanbetransformedintooneanotherusingasmallnumberoflow-costeditoperations,implyingthattheiroverallsyntacticstructureisfairlyiso-morphic.Furthermore,thecostofdeleting(orequivalentlyinserting)contextualelementsdependsontheirsemanticload.Forexample,termsrefertodomain-speciﬁcconceptsandassucharethemostimportantmeansofcommunicatingknowledgeinaspeciﬁcdomain.Therefore,theirdeletionisthecostliestoperation,indicatingthatimportantinformationislost.87TheremainderofSection4.2representsabriefreportonthesimilaritymeasure,whichhasbeenextensivelydescribedinSpasicandAnaniadou(2005).Thereadermaywishtoreadthisopen-accesspaperavailableathttp://helix-web.stanford.edu/psb05beforeproceedingtoSection4.3.8AlltypesofcontextelementsusedandthecostsofeditoperationsinvolvingthemarespeciﬁedinSpasicandAnaniadou(2005).2751Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "I.Spasicetal.EDusuallyreliesontheexactmatchesbetweensymbolsunless‘wildcard’symbolsareallowed.Thisisunsuitableforwordcom-parison,becausewordsareinﬂected.Also,thetermvariationphenomenoncancausesynonymoustermsnottomatch.WemadetheEDapproachmoreﬂexiblewithrespecttolexicalvariation.Forexample,twoinﬂectedwordformsmatchifboththeirlexicalcategor-iesandtheirbaseformsareidentical.Whentwotermsarecompared,informationfromtheontologyisutilized.AllsemanticclassesinUMLSareorganizedintoahierarchy,whichcanbeusedtoquantifytheirsimilarity.Thetreesimilarity(ts)betweentwoclassesC1andC2iscalculatedaccordingtothefollowingformula:ts(C1,C2)=2·common(C1,C2)depth(C1)+depth(C2)(1)wherecommon(C1,C2)denotesthenumberofcommonclassesinthepathsbetweentherootandthegivenclasses,anddepth(C)isthenumberofclassesinthepathconnectingtherootandthegivenclass.ThisformulaisaderivativeofDicecoefﬁcientwhereancestorclassesaretreatedastermfeatures.SincetheUMLSontologysupportsmul-tipleclassiﬁcationofterms,weestimatethesimilaritybetweentwotermsasthemaximalsimilaritybetweentheirclasses.Thesimilaritybetweentwotermsquantiﬁedinthismannerisusedtomodifytheirreplacementcostaccordingly.Thecalculationofthereplacementcostfortwoverbsdescribedintheontologyisanalogous.Theapproachusedintheontology-drivencomponentisapplicableonlytoclassiﬁedtermsandverbs.Currently,biomedicalontologiesareinherentlyincompleteduetothefast-growingnumberofterms.Therefore,itwouldbeusefultousecluesotherthantheonesexpli-citlystatedintheontologyinordertoextendthesemanticcomparisontounclassiﬁedtermsandverbs.Weexploitlexicalandmorpholo-gicalcluesastheyoftenindicatesemanticsimilarity.Forexample,5alpha-dihydrotestosteroneandtestosteronearelexicallysimilar,andthisfactcanbeusedtoinfertheirsemanticsimilarity.Weutil-izedthestandardEDapproachappliedatthecharacterlevelinordertoestimatelexicalsimilarity.Finally,theSOLDmeasureiscomputedusingthestandarddynamicprogrammingapproachforthecalculationofED(WagnerandFischer,1974).4.3RetrievalRetrievalinCBRservestoimprovetheefﬁciencyofthewholesystembyallowingforcrude(andcomputationallylessexpensive)compar-isonofanewcaseagainsttheonesstoredinthecase-base.Theresultisthesearchspaceconsiderablyreducedinsize.Finer(andcostlier)comparisonisthenperformedagainsttheretrievedcases.Ideally,theretrievedcasesshouldbetheonesmostsimilartothenewcase.However,thisisnotalwaysstraightforwardtoachieve,sothecompromiseshouldbemadebetweentwoconﬂictingobjectives:efﬁciencyandprecision.WenowdescribetheretrievalapproachusedinMaSTerClass.Letusrecallthat,givenanon-classiﬁedtermoccurringinaspeciﬁccon-text,wewouldliketoretrievetermsoccurringinsimilarcontexts.WepreviouslydescribedhowthecontextualsimilarityisassessedbyapplyingtheSOLDmeasure(SpasicandAnaniadou,2005).Wewouldliketoretrievethosecontextsthatwouldmostprobablymin-imizethevalueofthismeasure.Weadoptedaheuristicapproachexploringthenotionsofsemanticmatchingandterminologicalloadtoachievethisobjective.Termstendtoco-occurwithothertermsandverbsdenotingspe-ciﬁcrelationsbetweenthem.Termsanddomain-speciﬁcverbsalsocarrytheheaviestsemanticload.Thesefactsareusedtoretrieveothersimilarcontext(regardlessoftheirstructure)byusingthetermsandverbsfoundinthecontextoftheunclassiﬁedterm.Contextsmatchingsemanticallyaretheonesthatshareasufﬁcientnumberofterminologicallyrelevantelements(i.e.termsanddomain-speciﬁcverbs).Semanticmatchingmakesuseofterminologicalinformationandisontology-driven.Namely,inUMLS,bothtermsandverbsarehierarchicallyorganized.Thesehierarchiesareusedtoquantifythesimilaritybetweentermsandverbs[Formula(1)].Whenretrievingcontextsthroughsemanticmatching,termsandverbsfoundinitareusedtoretrievetheirclasses(andtheircloseancestors).Theresultingsetofclassesisthenusedtoretrievetheirinstances.9Alltermsandverbsobtainedinthismannerformasetofsemanticallymatchingtokens.Thesetokensarethenusedtoquerythecorpusinordertoretrievesemanticallysimilarcontexts(i.e.theonesthatcontainsufﬁ-cientnumberofsemanticallymatchingtokens).Letusexemplifytheprocessofsemanticmatchingbyconsideringthefollowingsentence:Radioinerttestosterone(T)and5alphadihydrotestosterone(DHT)butnotandrotenedione,progesterone,estradiol-17beta,estroneorcortisolina50-foldmolarexcessinhibited[3H]R1881bindingtotheARinspinalcord,heart,kidneyandRT.inwhichthetermtestosteroneneedstobeclassiﬁed.Letussup-posethattheitalicizedtermshavebeenidentiﬁed.Inaddition,letusassumethattheverbsinhibitandbindhavebeenidentiﬁedbythetagger.Thesetermsandverbsareusedtoretrieveothersim-ilartermsandverbs.Forexample,thetermprogesteroneclassiﬁedasahormoneisusedtoretrieveallothertermsfromthisclass,e.g.:thyrotropin-releasinghormone,glucocorticoid,endorphin,etc.Sim-ilarly,thetermARisusedtoretrieveitsexpandedformandrogenreceptorandallothertermsfromthereceptorclass,e.g.:thyroidhor-monereceptorbeta,thrombomodulin,nuclearreceptor,etc.Fortheverbinhibitthefollowingsimilarverbsareretrieved:prevent,stop,hinder,repress,impede,etc.Allretrievedtermsandverbsformasetofsemanticallymatchingtokens.Thesetokensarematchedagainstthecorpustoretrieveothersentencescontainingthem,suchas:NFI-CdoesnotrepressprogesteroneinductionoftheMMTVpromoterinHeLacells,suggestingthatprogesteroneinduc-tionofthepromoterdiffersmechanisticallyfromglucocorticoidinduction.9Forefﬁciencyreasons(e.g.whenclassesaretoolargemeasuredbythenumberoftheirinstances),a‘caching’approachcanbeusedinwhicheachclassiﬁedtermshouldbeannotatedinthecorpuswithapplicableclasslabels.Inthismanner,theretrievalofclassinstancesfromtheontologyisavoidedaswellasthesubsequentcomplex(measuredbythenumberofmatchingtokens)queriesagainstthecorpus.Instead,ontologyisusedonlytoretrievetheclasslabelsandusethemtosimplyquerythecorpuswiththegivenvaluesofclass-labelattributes.Furthermore,thisattributecanbeindexedtospeeduptheaccesstorelevanttermsinthecorpus.However,inthisapproachthecorpusshouldbeperiodicallyre-annotatedwithclassinformationinordertosynchronisethecorpuswithontologycontent,whichisastepnotneededintheoriginal‘dynamic’approach.2752Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "MaSTerClassFortwosentencestobesufﬁcientlyclosewithrespecttotheSOLDmeasure,itisdesirableforthemnotonlytosharesemanticallysim-ilartermsandverbs,butalsotohaveasimilarnumberofthem,sincetheirdeletionandinsertionarethecostliesteditoperations.Inordertotakethisfactintoaccountduringtheretrievalprocess,weintroducethenotionofterminologicalloaddeﬁnedasthenum-beroftermsanddomain-speciﬁcverbsinagivensentence.Givenaninputsentence,othersentenceswithsimilarterminologicalloadareretrieved.Obviously,theretrievalbasedontheterminologicalloaddoesnotconsiderthesemantictypesoftermsandverbs,butsimplytheirnumber.Inordertocompensateforthis,terminologicalloadiscombinedwithpreviouslydescribedsemanticmatching,thusretrievingsentencescontainingasimilarnumberofsimilartermsandverbs.4.4ClassiﬁcationOncethepotentiallysimilarsentencesareretrievedfromthecorpusandtheirsimilarityassessedbytheSOLDmeasure,themostsimilaronesareretainedbydynamicallysettingadistancethreshold(t)betweentheminimal(m)andaverage(a)valueoftheSOLDmeasurefortheretrievedsentences:t=m+(a−m)·d,whered(0≤d≤1)10isaparameterdetermininghowsimilartheselectedsentencesshouldbe.Thegreaterthevalueofd,thegreatertheacceptancerate.Multiplesentencesaretypicallyselectedtoperformclassiﬁcation.RecallthattheSOLDmeasureisamodiﬁcationofED,whichisbasedonthreetypesofeditoperations:insertion,deletionandreplacement.Anoptimalalignmentisasequenceoftheseopera-tions,whosetotalcostequalsthevalueofED.Notethattherecanbemorethanoneoptimalalignment.OptimalalignmentscanberetrievedfromthecostmatrixproducedwhencalculatingtheEDbythedynamicprogrammingmethod.Givenanoptimalalignment,twosentencesarealignedaccordingly.Insuchanalignment,weareinterestedinasyntacticelementalignedwiththeconsideredunclas-siﬁedterm.Whenitisalignedwithaclassiﬁedterm,wehypothesizethattheybelongtothesameclass(es).Theclassiﬁcationresultsobtainedseparatelyforeachsentencearecombinedthroughavotingprocedure.Theclasseswiththemajorityofvotesaresuggestedaspotentialclassesforthegiventerm.Tobeprecise,adynamicvotethresholdissetastheproductofthemaximalvotesreceivedbyaclassandtheparameterp(0≤p≤1),11thatdetermineswhatpercentageofthemaximalnumberofvotesreceivedisregardedacceptable.Ifp=0,thenallclasseswhichreceivedapositivenumberofvotesaresuggested.Ontheotherextreme,ifp=1,thenonlytheclass(es)(>1ifthereisatie)receivingthemaximalnumberofvotesaresuggested.Byusingtheparameterpweprovidedsupportformultipleclassiﬁcation.Itsupportsthefactthatbiomedicalconceptsoftenbelongtomultipleclassesdependingontheclassiﬁcationaspectused.Forexample,genescanbeclassi-ﬁedwithrespecttotheirfunction,subcellularlocationorphenotype[GeneOntology(http://www.geneontology.org)].Theontologyusedinthisworkincludestwomajorbranchesinthehierarchydependingonthepointofviewatachemical,whichcanbestructuralorfunc-tional.Manytermsareclassiﬁedinbothofthesesubhierarchies(e.g.manyhormonesarealsoclassiﬁedaspharmacologicsubstances).10Wehaveusedd=1.0intheexperimentsreportedlater.11Wehaveusedp=0.9intheexperimentsreportedlater.Table1.TheclassiﬁcationschemeChemicalviewedfunctionallyPharmacologicSubstanceAntibioticBiomedicalordentalmaterialBiologicallyactivesubstanceNeuroreactivesubstanceorbiogenicamineHormoneEnzymeVitaminImmunologicfactorReceptorIndicator,reagent,ordiagnosticaidHazardousorpoisonoussubstanceFig.3.AportionoftheUMLSSemanticNetwork:‘affects’hierarchyArun-throughexamplesummarizingthewholeclassiﬁcationprocessisgivenasSupplementarymaterial.5EVALUATION5.1ResourcesThecorpususedaspartofthecase-baseconsistsof2072abstractsonnuclearreceptorsretrievedfromMedline(2004).Eachabstractconsistsofasingletitleandanumberofsentences.Thetotalnumberofsentencesinthecorpus(notcountingthetitles)is19449.TheinitiallyPOS-taggedcorpushasbeenterminologicallyprocessed.WehavechosenUMLSastheclassiﬁcationschemefocusingonasubtreeof13classes,inwhichchemicalsareclassiﬁedaccordingtotheirfunctionalcharacteristics(Table1).Alloccurrencesof1643termscontainedintheUMLSdictionaryhavebeenannotated,resultinginatotalof24963annotatedtermoccurrences.Inaddition,theNC-valuemethod(FrantziandAnaniadou,1999)hasbeenappliedtorecognizetermsnotlistedinthedictionary.Atotalof2757termshavebeenrecognizedandannotatedinthecorpus,resultinginadditional28935annotatedtermoccurrences.Eachsentencehasbeenannotatedwithitsterminologicalload,theaveragevaluebeing3.21.Inaddition,eachsentencehasbeenpartiallyparsedinordertorecognizesyntacticstructuresofinterest.Asaresultofpartialparsing,eachsentenceisrepresentedasasequenceofblocks,theaveragenumberofblockspersentencebeing22.34.Inadditiontoterms,anontologyofverbswasconstructedusingthepartofUMLSSemanticNetworkthatorganizesdomain-speciﬁcrelationshipsintoahierarchy(Fig.3).Weusedthefactthattheserela-tionshipsareexpressedbyverbstoconvertthispartofUMLSintoan‘ontologyofverbs’.Weusedtheinitialhierarchyandthegivenverbsasastartingpointintowhichwemanuallyplacedadditionaldomain-speciﬁcverbs,handpickedfromthelistofhighfrequency2753Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "I.Spasicetal.Table2.TheevaluationsetupTermsNumberPercentage(oftotal)Percentage(ofclassiﬁed)Training1823633.8377.67Validation24054.4610.24Testing28385.2712.09Unclassiﬁed3041956.44—Total53898100.00—verbsextractedautomaticallyfromthecorpus.Theresultingonto-logycovers99inﬁnitiveformsofverbsdistributedacross23classes.Atotalof55581verboccurrenceshavebeenrecognizedoutofwhich14560havebeentreatedasdomainspeciﬁc.5.2EvaluationsetupTheclassiﬁcationexperimentswereperformedonlyfortermsfromthecorpusthatareclassiﬁedintheontologyinordertoautomatic-allyevaluatetheclassiﬁcationresults.Thecorrespondingconcepts(notterms)weredividedrandomlyintothreesets(usingtheapprox-imateratio15:15:70)andmappedintothesetsoftermstobeusedforvalidation,testingandtrainingrespectively.Table2summarizesthedistributionoftermoccurrencesacrossthetraining,validation,testingandnon-classiﬁedsetsofterms.5.3EvaluationmeasuresWeusedastandardsetofevaluationmeasurestoquantifytheresultsoftheclassiﬁcationexperiments.Thesemeasuresincludeprecision,recallandF-measure.Theprecisionandrecallarecalculatedforeachclassseparatelyaccordingtothefollowingtwoformulas:P=A/(A+B)(2)R=A/(A+C)(3)whereAisthenumberoftruepositives(thenumberoftimestheclasswascorrectlypredicted),Bisthenumberoffalsepositives(thenumberoftimestheclasswasincorrectlypredicted)andCisthenumberoffalsenegatives(thenumberoftimestheclasswasincorrectlynotpredicted).Theprecisionandrecallforallclassescollectivelycanbecalculatedthroughmacro-averagingormicro-averaging.Themacro-averagedprecisionandrecallarecalculatedbyaveragingtheprecisionandrecallobtainedforeachclassseparatelybyFormulas(2)and(3).Alternatively,whencalculatingthemicro-averagedvalues,thenumbersoftruepositives,falsepositivesandfalsenegativesobtainedforeachclassseparatelyaresummeduptoobtainthecorrespondingoverallnumbers.Themicro-averagedprecisionandrecallthencombinethesevaluesasbefore[Formulas(2)and(3)].Inallcases,theF-measureiscalculatedastheharmonicmeanofprecisionandrecall:F=2·P·R/(P+R).Theproblemofjudgingtheclassiﬁcationperformancebasedonthedescribedmeasuresisthattheyonlyconsiderwhetherthepre-dictedclassiscorrectornot,andconverselywhethertheactualclassispredictedornot.Thismaybetoocrudeforextensiveclas-siﬁcationschemes,becausetheprobabilityofacorrectpredictiondecreasesasthenumberofclassesincreases.Insuchcases,asimplemethodthatmapseveryinstancetothelargestclasscouldeasily‘outperform’other,moresubtleclassiﬁcationmethods,sincethenumberofcorrectlyclassiﬁedinstanceswouldbelargeaswell.How-ever,theusabilityofsuch‘better’resultsisseriouslyreduced,sincetheyoffernoinformationgain.However,amethodthatoftenfailstomakecorrectpredictions,butconsistentlymakespredictions‘close’tothecorrectclasses,canbemoreusefulbecauseitfocusesonthecorrectclassneighbourhood(asopposedtoasinglecorrectclass).Therefore,weintroduceaconceptofgradedprecisionandrecall,wherewemeasurethedistance(orsimilarity)betweenthepredictedandactualclassesratherthantheirequality.Sincetheclassiﬁcationschemeusedishierarchicallyorganized,weusedthetreesimilaritymeasure[Formula(1)]tomodifythenumeratorsinFormulas(2)and(3).Previously,thenumeratorAwasusedtocounttruepositivesforeachclassCinthefollowingmanner:A=(cid:1)at,wheretenumeratesthetestingtermoccurrences:atis1ifC∈predicted(t)∩actual(t)and0otherwise,wherepredicted(t)andactual(t)denotethesetsofpredictedandactualclasses,respectivelyforthegiventermt.Inourevaluationapproach,wewanttomeasurethedistancebetweenthepredictedandactualclassesratherthencomparingthembinary.Forexample,givenaclassC,foreachtestingtermoccurrencet,wecomparethegivenclasswiththeterm’sactualclasseslookingfortheminimaldistance:aPtiscalculatedasthemaximalvalueofts(C,CA)forallclassesCA∈actual(t)ifC∈predicted(t)and0otherwise.Inthismannerwemeasurethedegreeofincorrectness.Similarly,wecomparethegivenclasswithallpredictedclassesforeachtermtlookingfortheminimaldistanceinordertoestimatetherecall:aRtisassignedthemaximalvalueofts(C,CP)forallclassesCP∈predicted(t)ifC∈actual(t)and0otherwise.Wemeasurebyhowmuchthesystemmissedacorrectclass.Finally,thenumeratorsinFormulas(2)and(3)aremodiﬁedasfollows:AP=(cid:1)aptandAR=(cid:1)aRt,givingtheformulasforthegradedprecisionandrecall:GP=AP/(A+B)andGR=AR/(A+C).Finally,thevaluesobtainedforindividualclassesarecombinedasbeforetocalculatemacro-andmicro-averagedvalues.5.4BaselinemethodsWecomparetheresultsofourexperimentswiththoseobtainedbysixbaselinemethods.Wereliedonmethodscommonlyusedtoevaluateclassiﬁcationresults,suchasrandomclassiﬁerandthemethodthatassignsthelargestclasstoallobjectsofclassiﬁcation.Inaddition,weimplementedanaiveBayesclassiﬁerandarule-basedclassiﬁcationmethod.Theﬁrstbaselinemethod(B1)assignsarandomclasstoeachtermoccurrence.Thefollowingthreemethods(B2–B4)mapeachtermoccurrencetothelargestclassmeasuredbythenumberofitsconcepts,termsandtermoccurrencesrespectively.AnaiveBayesclassiﬁer(whosegoalistomaximizethecondi-tionalprobabilityofagiventermbeingassignedtoaspeciﬁcclassbasedonthefeaturesusedtorepresenttheterm)wasusedastheﬁfthbaselinemethod(B5).Eachtermisrepresentedasabagofco-occurringwords,i.e.allsinglewordsoccurringwiththegiventermwithinasentence.Theaforementionedconditionalprobabilityisthenestimatedastheproductoftheclassprobability(estimatedastheratiobetweenthenumberofalltermslabelledwiththegivenclassandthetotalnumberofterms)andtheconditionalprobabil-itiesoffeaturesgiventheclass(estimatedastheratiobetweenthenumberoftimesagivensinglewordco-occurswithtermsfromthegivenclassandthenumberofallsinglewordsco-occurringwithtermsfromthegivenclass).Finally,weusedrule-basedclassiﬁcation2754Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "MaSTerClassTable3.AsampleoftermclassiﬁcationrulesifTermcontainsawordstartingwithpreﬁx‘immun-’or‘anti-’thenclassis‘ImmunologicFactor’ifTermcontainsanyofthewords‘toxin’,‘insecticid’or‘pesticid’orawordstartingwithpreﬁx‘carcin-’,‘cancer-’or‘radioactiv-’thenclassis‘HazardousorPoisonousSubstance’ifTermcontainsawordendingwithsufﬁx‘-cyclin’or‘-mycin’thenclassis‘Antibiotic’(Table3)similartothatofFukudaetal.(1998)asthesixthbaselinemethod(B6).5.5ExperimentsWeconductedaseriesofthreeexperiments:E1,theCBRclassiﬁc-ationmethodusedinMaSTerClass;E2,thesamemethodsuppliedwithmoreextensivebiomedicalknowledge;E3,theCBRmethodcombinedwithclassiﬁcationrulesexploitingtheinternaltermchar-acteristics.ThehypothesisbehindtheexperimentE2isthattheknowledgecontainedintheontologymaynotbeequallydiscrim-inativeforallclasses.Inotherwords,precisionandrecallforindividualclassesmaydependonthecompletenessoftheonto-logyused.Broaderandmoreﬁne-grainedontologiesshouldhavehigherdiscriminativepower.Forexample,intheclassiﬁcationschemeused(Table1),receptorsareexpectedtoco-occurwithhor-monesandvitamins(bothclassesbeingpresentintheclassiﬁcationscheme),whereashazardousorpoisonoussubstancesareexpectedtoco-occurwithtermsdenotingdiseases,syndromes,poisoning,etc.(notcoveredbytheclassiﬁcationscheme).Totestthishypothesis,weexpandedtheclassiﬁcationschemewithotherclassesfoundinUMLS.TheunclassiﬁedtermoccurrenceswerematchedagainstthewholeUMLSontologyandtheretrievedinformationincorporatedintothesmallerontology.ThereasonwedidnotretagthecorpuswithalltermsfoundintheUMLS,butinsteadweonlyclassiﬁedalreadyannotatedunclassiﬁedterms,isthatwewantedtoexaminetheeffectsoftheclassiﬁcationinformationbeingattachedtotermsagainsttheabsenceofthisinformation.Atotalof2757originallyunclassiﬁedtermswereidentiﬁedinthecorpus,outofwhich547werefoundintheUMLS.Thesetermsresultedin186concepts,1329termvariantsand53classesbeingaddedtothecoreontologyusedfortheexperiments.Basedonthenewlyavailableclassiﬁcationinformation,6774termoccurrencesinthecorpuswereadditionallyannotatedasclassiﬁed.Withthelackofstrictnamingconventionsinbiomedicinereﬂect-ingparticularfunctionalpropertiesofterms,contextmayoftenbetheonlycluetotheirmeaning.Althoughtherearenogeneraltermin-ologicalstandardswhichwouldhelpdiscriminatebetweenspeciﬁcclassesoftermsinbiomedicine,therearenamingconventionsforsometypesofconceptsinthedomain,e.g.genes,allelesandpro-teins(Oliveretal.,2002).Theseconventionsareonlyguidelinesandassuchdonotimposerestrictionstoexperts.Still,whenaconceptisnamedbyatermthatisinaccordancewiththeprovidedconven-tions,thesecluesshouldbeexploitedratherthanbeneglectedinfavourofcontextualclues.Forexample,thesufﬁx-asecanbeusedtoidentifytermsdenotingenzymeswithhighprecision.Inanattempttoinvestigatetheeffectsofinternaltermcharacteristics,weanalysedthefeaturesoftermscontainedintheontologyandtriedtogeneralizeTable4.ThesummaryofexperimentsperformedExperimentDescriptionE1Core(case-basedreasoning)E2Core+extendedgeneralknowledgeE3Core+rulesB1RandomB2MajoritybythenumberofconceptsB3MajoritybythenumberoftermsB4MajoritybythenumberoftermoccurrencesB5NaiveBayesB6Rule-basedsomeofthemintoclassiﬁcationrules(Table3).Table4summarizestheexperimentsperformed.5.6ResultsTheexperimentalresultsareshowninTable5,inwhichP,RandFdenoteprecision,recallandF-measure,whileGP,GRandGFstandforthecorrespondinggradedmeasures.LetusﬁrstdiscussthehypothesisabouttheknowledgecontainedintheontologynotbeingequallydiscriminativetoallclassesbycomparingtheresultsgivenforexperimentsE1andE2.InexperimentE2,animprove-menthasbeennoticedinthemajorityoftheevaluationmeasuresused.Themostsigniﬁcantimprovementisthatofmacro-averagedprecisionduetotheprecisioneveningoutacrosstheclasses.Thedistributionoftruepositiveschangedbecausetheexpandedonto-logyhelpedtoimprovetheresultsforcertainclasses,whereastheyweredowngradedforothers.Thereasonfordeteriorationisthattheclassesfromtheoldontologyweremovedlowerdowninthenewontologywithrespecttotheroot,thusautomaticallyappearingmoresimilar[Formula(1)].Thenewtreesimilarityvaluesconsequentlyinﬂuencedthechangesintheresultsofapproximatecontextmatch-ing.However,thepositiveimpactofusingtheexpandedontologyoutbalancedthenegativeimpact,thusresultinginabetteroverallperformance.Theexpandedontologycontained66classes,whichis<50%of135classessupportedinUMLS.Inaddition,wedidnotusealltermsfromthe66classesmentioned,butonlythosealreadyannotatedinthecorpus.Weconcludethatthebestresultswouldbeachievedwithanontologythatcoversallaspectsofthedomain.IntheexperimentE3,thecoremethodhasbeencombinedwitharule-basedapproachexploitinginternaltermfeatures.Asigniﬁcantimprovementhasbeennoticedinallevaluationmeasuresused,sug-gestingthatinternalfeaturescancontributesigniﬁcantlytobetterclassiﬁcationperformance.Letusnowcomparetheresultsofourexperimentswiththoseachievedbythebaselinemethods.Inthemajorityofcases,ourmethodoutperformedthebaselinemethods.Thesigniﬁcantimprove-mentincomparisontotherandomclassiﬁersuggeststhatourmethodrepresentsareasonablystrongclassiﬁcationmethod.Similarly,ourcoremethodoutperformsthe‘majority’classiﬁcationmethodsonallmicro-averagedevaluationmeasures.Asforthemacro-averagedevaluationmeasures,thebaselinemethodsappeartohave‘better’precision.However,aclassiﬁcationmethodthatassignsaﬁxedclasstoallobjectsofclassiﬁcationwouldalwayshaveahighmacro-averagedprecisionwhenappliedagainstaclassiﬁcationschemewith2755Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "I.Spasicetal.Table5.ExperimentalresultsExperimentMacro-averagedMicro-averagedPRFGPGRGFPRFGPGRGFE145.9313.1620.4682.2162.8171.2142.9032.0736.7080.6167.4473.43E260.5019.7429.7786.7566.1375.0543.3832.6537.2581.0067.9973.92E363.8935.4845.6288.0971.0078.6367.9650.9058.2189.9475.8282.28B110.756.858.3764.1956.7760.2510.607.778.9763.9958.0360.86B294.977.6914.2397.1952.8268.4434.6725.4329.3463.4657.3960.27B392.317.6914.2097.5758.2172.920.050.030.0468.3960.9264.44B494.977.6914.2397.1952.8268.4434.6725.4329.3463.4657.3960.27B554.2210.3117.3382.2940.4054.1941.9518.1225.3183.1143.1456.80B693.5623.8538.0196.4627.3642.6398.9429.5845.5499.5731.5547.92multipleclasses;i.e.theclassprecisionwouldbe100%forallclassesotherthanthechosenﬁxedclass,resultingintheaverageclasspre-cisiongettingcloserto100%withthehighernumberofclasses.Inaddition,theaveragedprecisionisevenhigherwhentheﬁxedclassisamajorityclass,becauseitsclassprecisionwouldbehigher.Inthiscase,themacro-averagedprecisionprovidesmisleadingestimationofthequalityofclassiﬁcation,whichismadeobviousbylowmacro-averagedrecallvalues.Ingeneral,areliableconclusionabouttheclassiﬁcationqualitycannotbereachedbylookingatasingleeval-uationmeasure.Instead,asmanyevaluationmeasuresaspossibleshouldbetakenintoaccountinordertoprovideafullerinsight.Furthermore,themicro-averagedprecisionofourmethodissim-ilartothatofthenaiveBayesclassiﬁer.Althoughourmethoddidnotsigniﬁcantlyoutperformtheprecisionofthisbaselinemethod,thisfactisstilltakenasapositivefeatureofourclassiﬁcationapproach,becauseitiscomparablewiththemethodwhichmaximizestheprob-abilityofacorrectprediction.However,ourmethodsigniﬁcantlyoutperformstherecall(gradedrecallinparticular)ofthenaiveBayesclassiﬁer,whichresultsinbetteroverallperformanceestimatedbytheF-measure.TheonlymeasurewherethenaiveBayesclassiﬁersigniﬁcantlyoutperformedourmethodisthemacro-averagedpreci-sion.ThishappenedbecausethenaiveBayesclassiﬁerconcentratedonthemostprobableclasses(ingeneralandnotforspeciﬁctermoccurrencealone),whereastheleastprobableclasseswererarelysuggested.Therefore,theleastprobableclasseswereseldomusedtoproduceincorrectclassiﬁcations,thushavinghighclassprecision.Thisreﬂectedwellonthemacro-averagedprecision.Again,asingleevaluationmeasurecannotbeusedtofairlyjudgeaclassiﬁcationmethod.Forexample,inthiscase,otherevaluationmeasuresimplytheoverallpoorerqualitycomparedwithourclassiﬁcationmethod.Finally,letuscompareourapproachwiththerule-basedmethod.Ourmethodoutperformedthegivenbaselineonhalfoftheevaluationmeasures.Notsurprisingly,theprecisionofrule-basedclassiﬁca-tionisextremelyhigh.Thisisageneralcharacteristicofrule-basedclassiﬁcation.However,theoppositionbetweenprecisionandrecallisparticularlyapparentinsuchsystems.Namely,morerulestyp-icallyincreaserecallduetohighercoverage,butdecreasetheprecisionatthesametime.Ingeneral,therule-basedmethodprovidesbetterprecision,whileourmethodprovidesbetterrecall.Thebeneﬁtsofthesetwocomplementaryfeaturesareexploitedinahybridapproach(E3),whichsigniﬁcantlyimprovedtheprecisionofourCBRmethod,whilesigniﬁcantlyimprovingtherecalloftherule-basedmethod.TheF-measure(inallfourforms)forthecombinedmethodsigniﬁcantlyenhancestheF-measureforbothmethodsusedseparately.Basedonthecomparisonwiththesixbaselinemethods,weconcludethatourmethodprovidesastrongclassiﬁcationmodel.However,thereisroomforfurtherimprovement.Thebestresultshavebeenachievedwithadditionalknowledgeused,includingtheexpansionoftheoriginalontologyandtheuseofrulesgeneraliz-inginternaltermcharacteristicsintothecorrespondingclasses.Theresultssubstantiatethesuperiorityofthecombinedmethodincom-parisontothegivenbaselinemethods.However,furtherevaluationisneededwithmorediverseontologiesandlarge-sizecorpora.6DISCUSSIONANDCONCLUSIONSWeexploredtheuseofCBRfortheburningproblemoftermclas-siﬁcationinbiomedicine.Inparticular,wedescribedMaSTerClassasaspeciﬁcimplementationforthisproblem,whichclassiﬁesindi-vidualtermoccurrencesbylearninghowtolocateothersimilarcasesandextractlinguisticandbiomedicalinformationnecessarytoper-formclassiﬁcationfromthesecases.WedemonstratedthroughasetofexperimentsthataneffectiveandefﬁcientMLapproachcanbedevelopedandsuccessfullyemployedforthegivenproblem.Wemovedawayfromtheexistingclassiﬁcationapproachesinseveralaspects.First,mostoftheexistingapproachesdonotutilizehighdegreeofbiomedicalandlinguisticknowledge.Mostoften,theytargetspeciﬁcclassesbyexploitingsurfacefeatures(suchasortho-graphicorlexical)typicaloftheseclasses.Themainprobleminsuchapproachesistheobscurityofdiscriminativefeatures.Inourapproach,wemakeuseoflinguisticanddomain-speciﬁcfeatures,asbotharenecessaryforreliableclassiﬁcation.Thelinguisticknow-ledgeisappliedtoacquiresyntacticfeaturesoftermcontexts.Inaddition,oursystemefﬁcientlyutilizesexplicitandextensivebio-medicalknowledge.Whileothersystemsmayexplicitlyencodeacertaindegreeofbiomedicalknowledge,theyusuallydosothroughasetofrules.Suchknowledgerepresentationapproachesaretar-getedatspeciﬁctasksandclassesandassuchhavelimitedgeneralityandapplicability.Inourapproach,theknowledgeisrepresentedbyanontologywhichcomprisesinformationaboutconcepts(togetherwithtermsrepresentingthem),theirclassesandmutualrelations.Unlikerules,ontologiescanbeusedforvariousapplicationsbybothhumanusersandcomputers.Theeffortneededtoutilizeanexisting2756Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "MaSTerClassbiomedicalontologyinoursystemisconsiderablylowerthanthatrequiredtoengineersatisfactoryclassiﬁcationrules,whichmakesoursystemeasilyportablebetweendifferenttasksandsubdomains.Asopposedtotheexistingtermclassiﬁcationsystems,ratherthangeneralizingthebackgroundknowledge(bothbiomedicalandlin-guistic)intoacomplexsetofformalrulesguidingtheclassiﬁcationprocess,weoptedtoperformgeneralizationaspartoftheclassiﬁc-ationprocessbyrelatingtheunclassiﬁedtermoccurrencestogetherwiththeircontextstoclassiﬁedtermsoccurringinsimilarcontexts.Aﬂexibledistancemeasurehasbeendevelopedasawayofrelatingunclassiﬁedtorelevantclassiﬁedterms,whichcombineslinguisticanddomain-speciﬁcfeatures.Theﬂexibilityofthemethodreﬂectsinthefactthatsomefeaturescanbediscarded,whereasotherscanbechangedinanadhocmannertosuitspeciﬁccircumstances.However,thereisroomforfurtherimprovementofthesimilaritymeasureinordertotackletheproblemofdiscrepancybetweentheknowledgedescribedintheontologyandthatfoundintheliterature.Currently,lexicalsimilaritybasedonEDisusedasanalternativetosemanticcomparisonof‘unknown’terms,butitisnotalwaysappropriate,e.g.whenveryshorttermsaspotentialacronyms(2–4characters)arecomparedwithlongerterms,inwhichcasetheEDwouldresultinhighvaluesthatdonotreﬂectwellthesemanticsim-ilaritybetweenthetermsinvolved.Therefore,expandingacronymstotheirfullformscouldimprovetheoverallsimilarityforsomecases.However,acronymmatchingneedtobehandledwithspe-cialcaution,sincetheyareknowntobehighlyambiguous(e.g.ARcouldbeexpandedtoanyofthefollowingterms:androgenreceptor,amphiregulin,acyclicretinoid,agonist-receptor,adrener-gicreceptor,etc.).Theirpolysemycanbetackledbyquantifyingthematchbetweenanacronymandtheexpandedformwiththeprobab-ilityoftheirmatchestimatedfromthenumberofpossibleexpandedformsthroughacronymacquisitionandtermvariantmanagement(Nenadicetal.,2002).Inaddition,amoregeneralapproachtotheproblemscausedbysynonymyandpolysemywillbeusedinfutureversionsofthesystem,i.e.thelatentsemanticanalysiswillbeusedtoinfersemanticpropertiesoftermsbystatisticallyestimatingthecontextualusagesubstitutabilityofterms(Deerwesteretal.,1990).Furthermore,thepresentedapproachiscontext-sensitiveandassuchcanreadilybeutilizedfordisambiguationofbiomedicalterms(e.g.todistinguishbetweenhomonymousgenesandproteinstheyencode).Inthatsense,ourmethodismoregeneralthanothertermclassiﬁcationapproaches.Inourapproachweclassifyspeciﬁcoccur-rencesratherthangenericterms.Nonetheless,termsingeneralcanstillbeclassiﬁedbycollectingclassiﬁcationinformationobtainedfortheiroccurrences.Otherapproacheseitherdonotexploitthecontextatall(i.e.relyonlyontheinternaltermfeatures)orprocessthemcollectivelyratherthanfocusingonaspeciﬁctermoccurrenceanditscontext.Theformerapproachcannotbegenerallyusedfordisambiguation,becausetheappropriateinterpretationofanambigu-oustermcanbeinferredonlyfromitscontext.Similarly,thelatterapproachcannotbeusedfortermdisambiguationunlessthecontextsareclusteredsoastoreﬂectspeciﬁcaspectsoftermsusedinthem,whichrequiresadditionalprocessing.AnotheradvantageoftheMaSTerClasssystemistheabilitytolearnbystoringnewlysolvedclassiﬁcationproblemsforfutureuse,hencegraduallyimprovingitscompetence.Thesuggestedtermclas-siﬁcationapproachisinductiveinitsnature,thusbearingstrongresemblancetothehumanacquisitionoflanguage,whoarebelievednottoacquiretheirnativelanguagesthroughrules,butrathertolearnfromexamplesbyperforminganalogicalreasoning.Moreover,theusersareexpectedtoembracetheCBRsystemmorereadily,largelyduetothefactthatsimilarcasesreadilylendanexplanationforapar-ticularchoiceofsolutionbypresentingacontextinwhichasimilarsolutionproducedsatisfactoryresults.Inparticular,thevalidationoftheclassiﬁcationresultsandtheirincorporationintoanontologyaremadeeasier,becausethehumancuratorcanbeofferedanexplan-ationbypresentingthenewterm,itscontext,togetherwithothersimilartermsinsimilarcontexts.ACKNOWLEDGEMENTSI.S.gratefullyacknowledgessupportfromtheOverseasResearchStudentsAwardScheme(ORSAS),UK.S.A.issupportedbytheJISC-fundedNationalCentreforTextMining(NaCTeM),UK.AllauthorsexpresstheirgratitudetoDaiwaFoundationforenablingtheirscientiﬁccollaborationundertheDaiwaAdrianPrizescheme.REFERENCESAamodt,A.(1995)Knowledgeacquisitionandlearningfromexperience—theroleofcase-speciﬁcknowledge.InTecuci,G.andKodratoff,Y.(eds),MachineLearningandKnowledgeAcquisition;IntegratedApproaches.AcademicPress,NewYork,pp.197–245.Aha,D.(1998)Theomnipresenceofcase-basedreasoninginscienceandapplication.Knowledge-BasedSystems,11,261–273.Collier,N.etal.(2001)Automaticacquisitionandclassiﬁcationofterminologyusingataggedcorpusinthemolecularbiologydomain.J.Terminol.,7,239–257.Collier,N.andTakeuchi,K.(2004)Comparisonofcharacter-levelandpartofspeechfeaturesfornamerecognitioninbiomedicaltexts.J.Biomed.Inform.,37,423–435.Deerwester,S.etal.(1990)Indexingbylatentsemanticanalysis.J.Soc.Inform.Sci.,41,391–407.Frantzi,K.andAnaniadou,S.(1999)TheC-value/NC-valuedomainindependentmethodformultiwordtermextraction.J.Nat.Lang.Process.,6,145–180.French,J.,Powell,A.andSchulman,E.(1997)Applicationsofapproximatewordmatch-ingininformationretrieval.InGolshani,F.andMakki,K.(eds),Proceedingsofthe6thInternationalConferenceonKnowledgeandInformationManagement,LosAngeles,CA,ACM,NewYork,pp.9–15.Fukuda,K.,Tsunoda,T.,Tamura,A.andTakagi,T.(1998)Towardinformationextraction:identifyingprotein.InAltman,R.Keith,D.K.andHunter,L.(eds),ProceedingsofPSB,Hawaii,USA,WorldScientiﬁcPublishingCompany,Singapore,pp.705–716.Gierl,L.,Bull,M.andSchmidt,R.(1998)CBRinmedicine.InLenz,M.Bartsch-Spörl,B.,Burkhard,H.-D.andWess,S.(eds),Case-BasedReasoningTechnology:FromFoundationstoApplications.LNCS1400,Springer-Verlag,Berlin,pp.273–298.Globig,C.etal.(1997)Oncase-basedlearnabilityoflanguages.NewGenerationComput.,15,39–83.Gross,M.(1997)Theconstructionoflocalgrammars.InRoche,E.andSchabes,Y.(eds),FiniteStateLanguageProcessing.MITPress,CA,pp.329–352.Hatzivassiloglou,V.etal.(2001)Disambiguatingproteins,genesandRNAintext:amachinelearningapproach.Bioinformatics,1,97–106.Jurisica,I.andGlasgow,J.(2004)Applicationsofcase-basedreasoninginmolecularbiology.AIMagazine,25,85–95.Kazama,J.,Makino,T.,Ohta,Y.andTsujii,J.(2002)Tuningsupportvectormachinesforbiomedicalnamedentityrecognition.InJohnson,S.(ed.),ProceedingsoftheACLWorkshoponNaturalLanguageProcessingintheBiomedicalDomain,Philadelphia,PA,MorganKaufmann,pp.1–8.Kolodner,J.(1993)Case-BasedReasoning.MorganKaufmann.Leake,D.(1996)Case-basedreasoning:thepresentandfuture.InLeake,D.(ed),Case-BasedReasoning:Experiences,Lessons,andFutureDirections:AAAIPress/MITPress,CA.Lee,K.,etal.(2004)Biomedicalnamedentityrecognitionusingtwo-phasemodelbasedonSVMs.J.Biomed.Inform.,37,436–447.Macura,R.T.andMacura,K.(1997)Case-basedreasoning:opportunitiesandapplica-tionsinhealthcare.Artif.Intell.Med.,9,1–4.MEDLINE(2004).Nakagawa,H.andMori,T.(1998)Nestedcollocationandcompoundnounfortermrecog-nition.Proceedingsofthe1stWorkshoponComputationalTerminology,Montreal,Canada,pp.64–70.2757Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "I.Spasicetal.Nakagawa,H.andMori,T.(2003)Automatictermrecognitionbasedonstatisticsofcompoundnounsandtheircomponents.Terminology,9,201–219.Narayanaswamy,M.,Ravikumar,K.E.andVijay-Shanker,K.(2003)Abiologicalnamedentityrecognizer.InAltman,R.etal.(eds),ProceedingsofPSB,Hawaii,USA,WorldScientiﬁcPublishingCompany,Singapore,pp.427–438.Navarro,G.(2001)Aguidedtourtoapproximatestringmatching.ACMComput.Survey.,33,31–88.Navarro,G.,etal.(2000)Addingcompressiontoblockaddressinginvertedindexes.InformationRetrieval,3,49–77.Nedellec,C.(2002)Bibliographicalinformationextractioningenomics.IEEEIntelligentSyst.Trend.Controversies,17,76–80.Nenadic,G.,Spasic,I.andAnaniadou,S.(2002)Automaticacronymacquisitionandmanagementwithindomain-speciﬁctexts.Proceedingsofthe3rdInter-nationalConferenceonLanguage,ResourcesandEvaluation,LasPalmas,Spain,pp.2155–2162.Nobata,C.,Collier,N.andTsujii,J.(2000)Automatictermidentiﬁcationandclassiﬁca-tioninbiologytexts.ProceedingsoftheNaturalLanguagePaciﬁcRimSymposium,Beijing,China,pp.369–374.Oliver,D.,Rubin,D.,Stuart,J.,Hewett,M.,Klein,T.andAltman,R.(2002)Ontologydevelopmentforapharmacogeneticsknowledgebase.InAltman,R.Dunker,A.K.,Hunter,L.andKlein,T.E.(eds),ProceedingsofPSB,Hawaii,USA,WorldScientiﬁcPublishingCompany,Singapore,pp.65–76.Schmidt,R.etal.(2001)Cased-basedreasoningformedicalknowledge-basedsystems.Int.J.Med.Inform.,64,355–367.Spasic,I.andAnaniadou,S.(2005)Aﬂexiblemeasureofcontextualsimilarityforbio-medicalterms.InAltman,R.Jung,T.A.,Klein,T.E.,Dunker,A.K.andHunter,L.(eds),ProceedingsofPSB,Lihue,Hawaii,USA,WorldScientiﬁcPublishingCompany,Singapore,pp.197–208.Stapley,B.,Kelley,L.andSternberg,M.(2002)Predictingthesub-cellularlocationofproteinsfromtextusingsupportvectormachines.InAlt-man,R.Dunker,A.K.,Hunter,L.andKlein,T.E.(eds),ProceedingsofPSB,Hawaii,USA,WorldScientiﬁcPublishingCompany,Singapore,pp.374–385.Tsuruoka,Y.andTsujii,J.(2004)Improvingtheperformanceofdictionary-basedapproachesinproteinnamerecognition.J.Biomed.Inform.,37,461–470.Wagner,R.andFischer,M.(1974)Thestring-to-stringcorrectionproblem.J.ACM,21,168–173.Watson,I.andMarir,F.(1994)Case-basedreasoning:areview.KnowledgeEng.Rev.,9,327–354.2758Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\f",
      "\n"
     ]
    }
   ],
   "source": [
    "import io\n",
    " \n",
    "from pdfminer.converter import TextConverter\n",
    "from pdfminer.pdfinterp import PDFPageInterpreter\n",
    "from pdfminer.pdfinterp import PDFResourceManager\n",
    "from pdfminer.pdfpage import PDFPage\n",
    " \n",
    "def extract_text_from_pdf(pdf_path):\n",
    "    resource_manager = PDFResourceManager()\n",
    "    fake_file_handle = io.StringIO()\n",
    "    converter = TextConverter(resource_manager, fake_file_handle)\n",
    "    page_interpreter = PDFPageInterpreter(resource_manager, converter)\n",
    " \n",
    "    with open(pdf_path, 'rb') as fh:\n",
    "        for page in PDFPage.get_pages(fh, \n",
    "                                      caching=True,\n",
    "                                      check_extractable=True):\n",
    "            page_interpreter.process_page(page)\n",
    " \n",
    "        text = fake_file_handle.getvalue()\n",
    " \n",
    "    # close open handles\n",
    "    converter.close()\n",
    "    fake_file_handle.close()\n",
    " \n",
    "    if text:\n",
    "        return text\n",
    " \n",
    "if __name__ == '__main__':\n",
    "    print(extract_text_from_pdf('bti338.pdf'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11\n",
      "BIOINFORMATICS\n",
      "ORIGINALPAPER\n",
      "Vol.21no.112005,pages2748–2758\n",
      "doi:10.1093/bioinformatics/bti338Dataandtextmining\n",
      "MaSTerClass:acase-basedreasoningsystemforthe\n",
      "classiÞcationofbiomedicalterms\n",
      "IrenaSpasic\n",
      "1,,SophiaAnaniadou\n",
      "2andJunichiTsujii\n",
      "31SchoolofChemistry,TheUniversityofManchester,SackvilleStreet,POBox88,ManchesterM601QD,UK,\n",
      "2SchoolofComputing,ScienceandEngineering,TheUniversityofSalford,TheCrescent,SalfordM54WT,\n",
      "UKand\n",
      "3FacultyofInformationScienceandTechnology,TheUniversityofTokyo,7-3-1Hongo,Bunkyo-ku,\n",
      "Tokyo113-0033,Japan\n",
      "ReceivedonNovember19,2004;revisedonFebruary13,2005;acceptedonFebruary17,2005\n",
      "AdvanceAccesspublicationFebruary22,2005\n",
      "ABSTRACT\n",
      "Motivation:\n",
      "Thesheervolumeoftextuallydescribedbiomedical\n",
      "knowledgeexertstheneedfornaturallanguageprocessing(NLP)\n",
      "\n",
      "applicationsinordertoallowßexibleandefÞcientaccesstorelev-\n",
      "\n",
      "antinformation.Specializedsemanticnetworks(suchasbiomed-\n",
      "\n",
      "icalontologies,terminologiesorsemanticlexicons)cansigniÞcantly\n",
      "\n",
      "enhancetheseapplicationsbysupplyingthenecessaryterminological\n",
      "\n",
      "informationinamachine-readableform.Withtheexplosivegrowth\n",
      "\n",
      "ofbio-literature,newterms(representingnewlyidentiÞedconcepts\n",
      "\n",
      "orvariationsoftheexistingterms)maynotbeexplicitlydescribed\n",
      "\n",
      "withinthenetworkandhencecannotbefullyexploitedbyNLPapplic-\n",
      "\n",
      "ations.Linguisticandstatisticalcluescanbeusedtoextractmany\n",
      "\n",
      "newtermsfromfreetext.Theextractedtermsstillneedtobecor-\n",
      "\n",
      "rectlypositionedrelativetoothertermsinthenetwork.ClassiÞcation\n",
      "\n",
      "asameansofsemantictypingrepresentstheÞrststepinupdatinga\n",
      "\n",
      "semanticnetworkwithnewterms.\n",
      "\n",
      "Results:TheMaSTerClasssystemimplementsthecase-basedreas-\n",
      "oningmethodologyfortheclassiÞcationofbiomedicalterms.\n",
      "\n",
      "Availability:\n",
      "MaSTerClassisavailableathttp://www.cbr-masterclass.\n",
      "org.Itisdistributedunderanopensourcelicenceforeducationaland\n",
      "\n",
      "researchpurposes.ThesoftwarerequiresJava,JWDSP,Ant,MySQL\n",
      "\n",
      "andX-hivetobeinstalledandlicencesobtainedseparatelywhere\n",
      "\n",
      "needed.\n",
      "Contact:i.spasic@manchester.ac.uk\n",
      "Supplementaryinformation:\n",
      "Availableathttp://www.cbr-\n",
      "masterclass.org\n",
      "1INTRODUCTION\n",
      "Aterminology\n",
      "isacollectionofterms(denotingdomain-speciÞc\n",
      "conceptssuchasgenes,proteins,etc.)typicallyorganizedintoa\n",
      "\n",
      "classiÞcationhierarchy.Thecoreofsuchahierarchyisbasedonthe\n",
      "\n",
      "generalÐspeciÞcrelation.Otherrelations(e.g.biochemicalinterac-\n",
      "\n",
      "tions)areusedtocompletethemodelofaspeciÞcdomain.Concepts\n",
      "\n",
      "arenativelyassortedintogroups,either\n",
      "classes(whereallconcepts\n",
      "shareacommondescription)or\n",
      "clusters\n",
      "(groupsofcorrelatedcon-\n",
      "cepts),andtheorganizationoftermsinaterminologyneedstoreßect\n",
      "\n",
      "suchpropertiesconsistently.Itshouldalsobeextensiblesothatnew\n",
      "\n",
      "terms,representingnewlydiscoveredconcepts,canbeefÞciently\n",
      "\n",
      "incorporatedintotheexistingstructuresbyassociatingthemwith\n",
      "Towhomcorrespondenceshouldbeaddressed.\n",
      "otherterms.Theseassociationsshouldatleastincludethelinks\n",
      "\n",
      "betweenthecorrelatedterms,thusformingtheclustersofsemantic-\n",
      "\n",
      "allyrelatedterms,andthegeneralizationoftermssharingthesame\n",
      "\n",
      "setoffeaturesintoappropriateclasses.\n",
      "Givenacorpusofrelevanttextualdocuments,thetechniquesfor\n",
      "automatictermrecognition,clusteringandclassiÞcation,canhelpto\n",
      "\n",
      "automatetheprocessofcreatingandmaintainingaspeciÞctermino-\n",
      "\n",
      "logy.Theneedforautomationisparticularlyevidentinbiomedicine,\n",
      "\n",
      "wheremanualapproachescannotcopewithanenormousandever\n",
      "\n",
      "growingnumberoftermsandthecomplexstructureofbiomedical\n",
      "\n",
      "terminologies.1InthispaperwedescribeanapproachtoclassiÞcationofbiomed-\n",
      "icalterms,whoseresultscansupportautomaticterminologyupdate.\n",
      "\n",
      "Structuredup-to-dateterminologicalinformationcanthenbeused\n",
      "\n",
      "toimprovethequalityofnaturallanguageprocessingapplications\n",
      "\n",
      "(suchasinformationextractionandretrieval,documentclassiÞca-\n",
      "\n",
      "tionandsummarization,etc.),thusmakingiteasierforbiomedical\n",
      "\n",
      "expertstonavigatethroughhugevolumesofscientiÞcdocuments.\n",
      "2AutomaticclassiÞcationofbiomedicaltermsisdifÞcultdueto\n",
      "loosenamingconventions,whichrarelyaimtoencodeparticular\n",
      "\n",
      "functionalpropertiesoftheunderlyingconceptsinasystematic\n",
      "\n",
      "manner.\n",
      "3Forthecomplexityreasonscausedbyinconsistentand\n",
      "imprecisenamingpractice,manymethodsdevelopedforclassiÞca-\n",
      "\n",
      "tionofbiomedicaltermstargetonlyalimitednumberofspeciÞc\n",
      "\n",
      "classesthroughmanualidentiÞcationoffeaturestypicaloftheir\n",
      "\n",
      "terms.Forexample,Fukuda\n",
      "etal\n",
      ".(1998)developedarule-based\n",
      "methodfortherecognitionofproteinnamesexploringtheirortho-\n",
      "\n",
      "graphicandlexicalfeatures(e.g.capitalletters,digitsandspecial\n",
      "\n",
      "characters).Aseriesofmethodshavebeenimplementedfollowing\n",
      "\n",
      "thisidea.Forinstance,Narayanaswamy\n",
      "etal\n",
      ".(2003)extended\n",
      "1UMLS(http://www.nlm.nih.gov/research/umls)containsoveronemillion\n",
      "conceptsnamedby5millionterms,organizedintoahierarchyof135classes\n",
      "\n",
      "andinterconnectedby54differentrelations.\n",
      "2Medline(http://www.ncbi.nlm.nih.gov/PubMed)refersto\n",
      "12million\n",
      "journalarticles,expandingformorethan10000referencesweekly.Over\n",
      "\n",
      "571000referenceswereaddedin2004.\n",
      "3Thereisnoexactconsensusonwhatconstitutesabiomedicaltermeven\n",
      "whenitisrestrictedto,e.g.proteinsandgenes(Narayanaswamy\n",
      "etal\n",
      ".,2003),\n",
      "althoughthenamingconventionsdoexistfortheseconcepts(Oliver\n",
      "etal\n",
      ".,2002).2748©TheAuthor2005.PublishedbyOxfordUniversityPress.Allrightsreserved.ForPermissions,pleaseemail:journals.permissions@oupjournals.o\n",
      "rgDownloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\n"
     ]
    }
   ],
   "source": [
    "import PyPDF2\n",
    "# pdf file object\n",
    "# you can find find the pdf file with complete code in below\n",
    "pdfFileObj = open('bti338.pdf', 'rb')\n",
    "# pdf reader object\n",
    "pdfReader = PyPDF2.PdfFileReader(pdfFileObj)\n",
    "# number of pages in pdf\n",
    "print(pdfReader.numPages)\n",
    "# a page object\n",
    "pageObj = pdfReader.getPage(0)\n",
    "# extracting text from page.\n",
    "# this will print the text you can also save that into String\n",
    "print(pageObj.extractText())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "BIOINFORMATICS ORIGINAL PAPER Vol. 21 no. 11 2005, pages 2748–2758\n",
      "\n",
      "doi:10.1093/bioinformatics/bti338\n",
      "\n",
      "Data and text mining\n",
      "\n",
      "MaSTerClass: a case-based reasoning system for the\n",
      "classiﬁcation of biomedical terms\n",
      "Irena Spasic1,∗, Sophia Ananiadou2 and Junichi Tsujii3\n",
      "1School of Chemistry, The University of Manchester, Sackville Street, PO Box 88, Manchester M60 1QD, UK,\n",
      "2School of Computing, Science and Engineering, The University of Salford, The Crescent, Salford M5 4WT,\n",
      "UK and 3Faculty of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku,\n",
      "Tokyo 113-0033, Japan\n",
      "\n",
      "Received on November 19, 2004; revised on February 13, 2005; accepted on February 17, 2005\n",
      "\n",
      "Advance Access publication February 22, 2005\n",
      "\n",
      "ABSTRACT\n",
      "Motivation: The sheer volume of\n",
      "textually described biomedical\n",
      "knowledge exerts the need for natural language processing (NLP)\n",
      "applications in order to allow ﬂexible and efﬁcient access to relev-\n",
      "ant information. Specialized semantic networks (such as biomed-\n",
      "ical ontologies, terminologies or semantic lexicons) can signiﬁcantly\n",
      "enhance these applications by supplying the necessary terminological\n",
      "information in a machine-readable form. With the explosive growth\n",
      "of bio-literature, new terms (representing newly identiﬁed concepts\n",
      "or variations of the existing terms) may not be explicitly described\n",
      "within the network and hence cannot be fully exploited by NLP applic-\n",
      "ations. Linguistic and statistical clues can be used to extract many\n",
      "new terms from free text. The extracted terms still need to be cor-\n",
      "rectly positioned relative to other terms in the network. Classiﬁcation\n",
      "as a means of semantic typing represents the ﬁrst step in updating a\n",
      "semantic network with new terms.\n",
      "Results: The MaSTerClass system implements the case-based reas-\n",
      "oning methodology for the classiﬁcation of biomedical terms.\n",
      "Availability: MaSTerClass is available at http://www.cbr-masterclass.\n",
      "org. It is distributed under an open source licence for educational and\n",
      "research purposes. The software requires Java, JWDSP, Ant, MySQL\n",
      "and X-hive to be installed and licences obtained separately where\n",
      "needed.\n",
      "Contact: i.spasic@manchester.ac.uk\n",
      "Supplementary\n",
      "masterclass.org\n",
      "\n",
      "http://www.cbr-\n",
      "\n",
      "information:\n",
      "\n",
      "Available\n",
      "\n",
      "at\n",
      "\n",
      "1 INTRODUCTION\n",
      "A terminology is a collection of terms (denoting domain-speciﬁc\n",
      "concepts such as genes, proteins, etc.) typically organized into a\n",
      "classiﬁcation hierarchy. The core of such a hierarchy is based on the\n",
      "general–speciﬁc relation. Other relations (e.g. biochemical interac-\n",
      "tions) are used to complete the model of a speciﬁc domain. Concepts\n",
      "are natively assorted into groups, either classes (where all concepts\n",
      "share a common description) or clusters (groups of correlated con-\n",
      "cepts), and the organization of terms in a terminology needs to reﬂect\n",
      "such properties consistently. It should also be extensible so that new\n",
      "terms, representing newly discovered concepts, can be efﬁciently\n",
      "incorporated into the existing structures by associating them with\n",
      "\n",
      "∗To whom correspondence should be addressed.\n",
      "\n",
      "other terms. These associations should at least include the links\n",
      "between the correlated terms, thus forming the clusters of semantic-\n",
      "ally related terms, and the generalization of terms sharing the same\n",
      "set of features into appropriate classes.\n",
      "\n",
      "Given a corpus of relevant textual documents, the techniques for\n",
      "automatic term recognition, clustering and classiﬁcation, can help to\n",
      "automate the process of creating and maintaining a speciﬁc termino-\n",
      "logy. The need for automation is particularly evident in biomedicine,\n",
      "where manual approaches cannot cope with an enormous and ever\n",
      "growing number of terms and the complex structure of biomedical\n",
      "terminologies.1\n",
      "\n",
      "In this paper we describe an approach to classiﬁcation of biomed-\n",
      "ical terms, whose results can support automatic terminology update.\n",
      "Structured up-to-date terminological information can then be used\n",
      "to improve the quality of natural language processing applications\n",
      "(such as information extraction and retrieval, document classiﬁca-\n",
      "tion and summarization, etc.), thus making it easier for biomedical\n",
      "experts to navigate through huge volumes of scientiﬁc documents.2\n",
      "Automatic classiﬁcation of biomedical terms is difﬁcult due to\n",
      "loose naming conventions, which rarely aim to encode particular\n",
      "functional properties of the underlying concepts in a systematic\n",
      "manner.3 For the complexity reasons caused by inconsistent and\n",
      "imprecise naming practice, many methods developed for classiﬁca-\n",
      "tion of biomedical terms target only a limited number of speciﬁc\n",
      "classes through manual identiﬁcation of features typical of their\n",
      "terms. For example, Fukuda et al. (1998) developed a rule-based\n",
      "method for the recognition of protein names exploring their ortho-\n",
      "graphic and lexical features (e.g. capital letters, digits and special\n",
      "characters). A series of methods have been implemented following\n",
      "this idea. For instance, Narayanaswamy et al. (2003) extended\n",
      "\n",
      "1UMLS (http://www.nlm.nih.gov/research/umls) contains over one million\n",
      "concepts named by 5 million terms, organized into a hierarchy of 135 classes\n",
      "and interconnected by 54 different relations.\n",
      "refers to ∼12 million\n",
      "2Medline (http://www.ncbi.nlm.nih.gov/PubMed)\n",
      "journal articles, expanding for more than 10 000 references weekly. Over\n",
      "571 000 references were added in 2004.\n",
      "3There is no exact consensus on what constitutes a biomedical term even\n",
      "when it is restricted to, e.g. proteins and genes (Narayanaswamy et al., 2003),\n",
      "although the naming conventions do exist for these concepts (Oliver et al.,\n",
      "2002).\n",
      "\n",
      "2748\n",
      "\n",
      "© The Author 2005. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oupjournals.org\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "/\n",
      "\n",
      "f\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "\f",
      "Fukuda’s approach to six classes of biomedical entities: gene or pro-\n",
      "tein, gene or protein part, chemical, chemical part, source and others.\n",
      "The main problem in such approaches is that term classiﬁcation rules\n",
      "are often obscure and imprecise due to loose naming conventions.\n",
      "\n",
      "In order to cope efﬁciently with the complexity of knowledge\n",
      "needed to perform reliable classiﬁcation, many approaches resort\n",
      "to machine learning (ML) techniques to detect features that char-\n",
      "the ML term classiﬁcation\n",
      "acterize speciﬁc classes. Currently,\n",
      "methods exploit little or no biomedical knowledge for guided learn-\n",
      "ing. Usually, general-purpose ML algorithms are applied to shallow\n",
      "representation of text (Nedellec, 2002). For instance, Stapley et al.\n",
      "(2002) used a support vector machine (SVM) approach with a\n",
      "non-structured representation of text to classify gene names (rep-\n",
      "resented as vectors of contextual features, deﬁned as single words\n",
      "co-occurring in the same abstract) with respect to their subcellular\n",
      "location. Recently, there have been a number of other applications of\n",
      "SVMs for classiﬁcation of biomedical terms (Kazama et al., 2002;\n",
      "Lee et al., 2004; Collier and Takeuchi, 2004). These approaches dif-\n",
      "fer from those of Stapley et al. (2002) with respect to the features\n",
      "used which largely resemble those proposed by Fukuda et al. (1998).\n",
      "Alternatively, probabilistic methods such as naive Bayes classiﬁca-\n",
      "tion (Hatzivassiloglou et al., 2001; Nobata et al., 2000) and hidden\n",
      "Markov models (Collier et al., 2001) have been used.\n",
      "\n",
      "All mentioned methods require large amounts of training data and\n",
      "signiﬁcant training time to prevent overﬁtting. Namely, they are\n",
      "optimized to ﬁt the training data, which may not be ideal approx-\n",
      "imation of the real data. Thus, such algorithms require large training\n",
      "sets and need to be periodically retrained upon the advent of new data.\n",
      "They also underperform for minority classes due to the data sparsity\n",
      "problem. Furthermore, they explicitly differentiate between the train-\n",
      "ing phase (in which classiﬁcation rules are learnt) and the application\n",
      "phase (in which the learnt rules are applied). However, satisfact-\n",
      "ory rules cannot always be produced (e.g. due to weak correlation\n",
      "between term features and their classes).\n",
      "\n",
      "In this paper we suggest an alternative ML approach. Case-based\n",
      "reasoning (CBR) is particularly suitable for the problem of term clas-\n",
      "siﬁcation in biomedicine, because it is pragmatic and robust enough\n",
      "to deal with the complexity of both natural language and the biomed-\n",
      "ical domain as explained in the following section which outlines the\n",
      "basic principles of this methodology.\n",
      "\n",
      "2 METHODOLOGY\n",
      "\n",
      "CBR is based on remembering speciﬁc experiences that may be useful for the\n",
      "problem (case) being solved. It may be viewed as a multistage cycle involving\n",
      "the four ‘re-’ (Aamodt, 1995): (1) retrieve the most similar case, (2) reuse the\n",
      "case to solve the new problem, (3) revise the suggested solution and (4) retain\n",
      "the useful information obtained during problem solving. Therefore, new prob-\n",
      "lems are solved by adapting solutions that provided satisfactory results for\n",
      "similar problems, thus avoiding the need for an explicit model of the problem\n",
      "domain (Watson and Marir, 1994). Instead, only features relevant in the con-\n",
      "text of the current problem need to be identiﬁed. Therefore, CBR makes use\n",
      "of speciﬁc (as opposed to generalized) knowledge in both problem solving\n",
      "and learning (Kolodner, 1993). Speciﬁc information about the past experi-\n",
      "ences is regarded as knowledge, unlike in rule-based or model-based systems,\n",
      "where it is treated as data. In this manner, CBR tackles the main issues in\n",
      "other ML systems, such as the lack of robustness and ﬂexibility, conﬁne-\n",
      "ment to narrow problem domains and difﬁcult development and maintenance\n",
      "(Aamodt, 1995).\n",
      "\n",
      "Memory forms a basis for the learning ability of CBR systems (Watson\n",
      "and Marir, 1994). Nevertheless, such a trivial form of learning still supports\n",
      "\n",
      "MaSTerClass\n",
      "\n",
      "generalization and abstraction implicitly through the use of similarity\n",
      "(Aamodt, 1995). Therefore, a CBR system is capable of learning without\n",
      "explicitly generalizing speciﬁc cases into formulas, rules or other symbolic\n",
      "representations (Globig et al., 1997). Such a lazy or demand-driven approach\n",
      "has the following advantages (Aha, 1998; Leake, 1996): easier knowledge\n",
      "acquisition, reduced problem solving predisposition, incremental learning\n",
      "and improved user acceptance due to explanation based on precedents.\n",
      "\n",
      "The general advantages of CBR are particularly emphasized in the family\n",
      "of biomedical sciences because of the homologous nature of biological sys-\n",
      "tems rooted in evolution (Jurisica and Glasgow, 2004). Therefore, biomedical\n",
      "experts themselves often use analogical reasoning to plan and conduct exper-\n",
      "iments exploring similarities between new and known systems. Furthermore,\n",
      "biomedical ﬁeld is overwhelmed by data but often lacks exact and complete\n",
      "theories that could interpret such amounts of data correctly and efﬁciently.\n",
      "For example, due to huge amounts of data, many unknowns, incomplete\n",
      "theories and extremely dynamic nature of molecular biology, reasoning in\n",
      "this domain is often based on experience as opposed to general knowledge.\n",
      "CBR has been successfully applied in molecular biology to solve a variety\n",
      "of problems, e.g. protein crystallization, genomic sequence analysis, protein\n",
      "structure determination, etc.\n",
      "\n",
      "Similarly, Schmidt et al. (2001) emphasize the appropriateness of CBR\n",
      "for medical domain using an argument that the knowledge of medical experts\n",
      "is ‘a mixture of textbook knowledge and experience’. The textbook know-\n",
      "ledge can be represented by rules or other models, while the experience can\n",
      "be represented by cases. Moreover, medical cases are professionally docu-\n",
      "mented resulting in an invaluable repository of information, where CBR can\n",
      "be used as ‘an engine for intelligent text processing and retrieval, data mining\n",
      "and projective reasoning’ in order to fully exploit available information espe-\n",
      "cially in the age of electronic patient records (Macura and Macura, 1997).\n",
      "Furthermore, the typical decision making process of a medical practitioner\n",
      "involves reasoning with cases, which establishes medicine as an interaction\n",
      "of research and practice, where clinical practice is characterized by a collec-\n",
      "tion of accumulated cases. CBR and its learning strategy mirror the learning\n",
      "process of a medical practitioner when faced with different cases (patients,\n",
      "symptoms, diseases and treatments). Hence, cognitive adequateness and\n",
      "explicit representation of experience make CBR a natural ML approach\n",
      "in medicine (Gierl et al., 1998). This fact has been restated by numerous\n",
      "medical applications including diagnosis, classiﬁcation, planning, prognosis,\n",
      "tutoring, etc.\n",
      "\n",
      "In view of our speciﬁc problem of classifying biomedical terms, CBR can\n",
      "readily utilize the large body of biomedical texts as the training data without\n",
      "the need to map term features to the corresponding classes, a priori. Instead,\n",
      "generalization (or learning) is performed on demand based on the currently\n",
      "available data and with respect to a particular term being classiﬁed. This helps\n",
      "to reduce overﬁtting, which in other ML approaches stems from an attempt to\n",
      "generalize in advance so as to ﬁt most of the available training data. Moreover,\n",
      "by automatically adapting to the data available at the moment of classiﬁcation\n",
      "and not training, the need for retraining is avoided in CBR. These properties\n",
      "particularly suit the dynamic nature of the biomedical domain (new data\n",
      "become available daily) and the difﬁculty in generalizing term properties into\n",
      "corresponding classes (due to loose naming conventions and the variability\n",
      "of natural languages).\n",
      "\n",
      "Having chosen CBR as a methodology for classiﬁcation of biomedical\n",
      "terms, the next step is to decide how to utilize it for this problem. First,\n",
      "note that there is a large amount of electronically available biomedical\n",
      "documents describing speciﬁc discoveries and a number of knowledge repos-\n",
      "itories describing general biomedical knowledge. The biomedical knowledge\n",
      "repositories, although typically incomplete, still contain large volumes of\n",
      "information in a structured form. On the other side, scientiﬁc documents\n",
      "contain comprehensive up-to-date information structured by the natural lan-\n",
      "guage rules. Our intention was to use a corpus of biomedical texts (in which\n",
      "known terms are classiﬁed within a biomedical ontology) as a collection of\n",
      "classiﬁcation experiences and perform classiﬁcation of new terms by making\n",
      "analogies on the ﬂy. The role of an ontology in this context is to provide a\n",
      "classiﬁcation scheme, aid semantic interpretation of domain-speciﬁc text and\n",
      "\n",
      "2749\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "/\n",
      "\n",
      "f\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "\f",
      "unclassified\n",
      "term\n",
      "occurrence\n",
      "\n",
      "case-base\n",
      "\n",
      "annotated corpus\n",
      "\n",
      "I.Spasic et al.\n",
      "\n",
      " \n",
      "term (class)\n",
      "+\n",
      " \n",
      "context\n",
      "classified\n",
      " \n",
      "case\n",
      "\n",
      "g\n",
      "n\n",
      "i\n",
      "t\n",
      "o\n",
      "v\n",
      "\n",
      "new case\n",
      "\n",
      "term (---)\n",
      "+\n",
      "context\n",
      "\n",
      "l\n",
      "\n",
      "a\n",
      "v\n",
      "e\n",
      "i\n",
      "r\n",
      "t\n",
      "e\n",
      "r\n",
      "\n",
      "y\n",
      "t\n",
      "i\n",
      "r\n",
      "a\n",
      "m\n",
      "s\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "term (class)\n",
      "+\n",
      "context\n",
      "\n",
      "retrieved\n",
      "cases\n",
      "\n",
      "linguistic\n",
      "knowledge\n",
      "\n",
      "domain-specific\n",
      "knowledge\n",
      "\n",
      "general knowledge\n",
      "\n",
      "matched\n",
      "cases\n",
      "\n",
      "term (class)\n",
      "+\n",
      "context\n",
      "\n",
      "matching\n",
      "\n",
      "similar\n",
      "cases\n",
      "\n",
      "term (class)\n",
      "+\n",
      "context\n",
      "\n",
      "Fig. 1. The MaSTerClass system organization.\n",
      "\n",
      "support the semantic aspect of the similarity measure used to identify term\n",
      "contexts similar to the one used for the classiﬁcation of a new term.\n",
      "\n",
      "3 THE MaSTerClass SYSTEM\n",
      "In this section, we introduce the MaSTerClass (machine supported\n",
      "term classiﬁcation) system. Although CBR served as the methodo-\n",
      "logical framework, the actual techniques needed to be developed\n",
      "speciﬁcally for the given problem. Figure 1 depicts the organiz-\n",
      "ation and the workﬂow of MaSTerClass. Two types of general\n",
      "knowledge (linguistic and domain-speciﬁc) are utilized. The lin-\n",
      "guistic knowledge is used to structure textual information, i.e. to\n",
      "extract the underlying syntactic structure and represent it explicitly\n",
      "in a machine-usable form. A corpus of biomedical abstracts was\n",
      "automatically annotated with lexical, syntactic and terminological\n",
      "information. The rules for recognizing syntactic structures of interest\n",
      "(e.g. noun and verb phrases) have been speciﬁed by the correspond-\n",
      "ing local grammars (Gross, 1997). Terms have been identiﬁed in\n",
      "the corpus by looking up the UMLS4 dictionary and applying the\n",
      "NC-value5 method. The domain-speciﬁc knowledge adopted from\n",
      "UMLS consists of terms and the corresponding concepts (i.e. concept\n",
      "identiﬁers) organized into a classiﬁcation hierarchy.\n",
      "\n",
      "4UMLS is an ontology, which merges over 100 biomedical vocabularies aim-\n",
      "ing to facilitate the development of information systems for text processing in\n",
      "biomedicine by providing a formal representation of domain-speciﬁc know-\n",
      "ledge in order to process, retrieve, integrate, and aggregate biomedical data\n",
      "and information contained in the relevant literature.\n",
      "5The NC-value (Frantzi and Ananiadou, 1999) method extracts multiword\n",
      "terms [>85% of terms are multiword (Nakagawa and Mori, 2003)] by\n",
      "using linguistic knowledge to propose term candidates through their form-\n",
      "ation patterns followed by frequency-based analysis used to estimate their\n",
      "‘termhood’.\n",
      "\n",
      "2750\n",
      "\n",
      "Note that the functionality of the MaSTerClass system covers\n",
      "term classiﬁcation only. While we currently use UMLS and the\n",
      "NC-value method to annotate the corpus terminologically, they are\n",
      "external to the system and by no means part of it. The same remark\n",
      "applies to the use of other linguistic tools, such as tagger and\n",
      "parser. In other words, any other tagger, parser or term recognition\n",
      "method can be used just as well without the need for reimplement-\n",
      "ation. Similarly, any other ontology could generally be converted\n",
      "into our internal format and stored into the database used by the\n",
      "system.\n",
      "\n",
      "The annotated corpus of biomedical abstracts used in combination\n",
      "with the UMLS ontology forms the case-base of the MaSTerClass\n",
      "system. It is used for term classiﬁcation by remembering speciﬁc\n",
      "classiﬁcation contexts that can be useful for the term currently being\n",
      "classiﬁed. New terms are classiﬁed by adapting (or more precisely,\n",
      "adopting) the classes of similar terms in similar contexts. Each case\n",
      "in this approach consists of a term occurring in a speciﬁc context\n",
      "(description of the problem) and one or more classes that apply to\n",
      "that term occurrence (solution).\n",
      "\n",
      "It would not be efﬁcient (or even feasible) to compare a new term to\n",
      "all available terms and their contexts. For this reason, only potentially\n",
      "similar contexts are retrieved by using terminological information\n",
      "from the ontology to locate other contexts containing semantically\n",
      "similar terms and domain-speciﬁc verbs. The new case is compared\n",
      "with each retrieved case by the SOLD (syntactic, ontology-driven\n",
      "and lexical distance) measure, which compares their syntactic and\n",
      "semantic properties. It is based on the concept of the edit distance\n",
      "(ED), which has been widely used for approximate string match-\n",
      "ing (Navarro, 2001). It compares two strings through the minimal\n",
      "number (or cost) of edit operations (including deletion/insertion\n",
      "of a character and the replacement of two characters in the two\n",
      "strings). The SOLD measure uses the same operations, but applies\n",
      "them to syntactic elements (obtained through lexical tagging and\n",
      "partial syntactic parsing) and terms (obtained automatically by the\n",
      "NC-value method or dictionary look-up). Both linguistic and ter-\n",
      "minological knowledge are used to approximately match individual\n",
      "context elements.\n",
      "\n",
      "The most similar retrieved cases are selected for further pro-\n",
      "cessing. The selection process,\n",
      "thus, further reduces the search\n",
      "space to be processed in the matching phase, in which the new\n",
      "case and old cases are aligned according to the combinations of\n",
      "edit operations resulting in the minimal alignment cost. The pur-\n",
      "pose of alignment is to match the unclassiﬁed term to a classiﬁed\n",
      "term that has a similar role in a similar context (both syntactically\n",
      "and semantically). The successfully matched cases are used collect-\n",
      "ively to propose the class(es) for the unclassiﬁed term through a\n",
      "voting procedure. Each case contributes to the ﬁnal classiﬁcation\n",
      "results by delegating votes for the classes attached to the matched\n",
      "classiﬁed term. For example, in Figure 2 let us suppose that the\n",
      "unclassiﬁed term 5 alpha-dihydrotestosterone is aligned with the\n",
      "term testosterone classiﬁed as hormone. Then the class suggested\n",
      "for 5 alpha-dihydrotestosterone by this alignment is hormone as\n",
      "well. As multiple cases are used, it is expected that any outlying\n",
      "cases that got through retrieval, selection and matching would be\n",
      "outvoted at this stage. Finally, the classes receiving most votes are\n",
      "suggested for the given unclassiﬁed term. Following a validation pro-\n",
      "cedure performed by a human curator, the newly learnt case (i.e. the\n",
      "term successfully classiﬁed based on its context) can be added to the\n",
      "case-base.\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "/\n",
      "\n",
      "f\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "\f",
      "testosterone \n",
      "5 alpha-dihydrotestosterone \n",
      "\n",
      "but  not \n",
      "---- \n",
      "---- \n",
      "\n",
      "progesterone \n",
      "---------------- \n",
      "\n",
      "inhibits \n",
      "inhibited \n",
      "\n",
      "[3H]R1881 \n",
      "[3H]R1881 \n",
      "\n",
      "binding \n",
      "binding \n",
      "\n",
      "to \n",
      "to \n",
      "\n",
      "AR \n",
      "the androgen receptor \n",
      "\n",
      "---  ------- \n",
      "in  kidney \n",
      "\n",
      "MaSTerClass\n",
      "\n",
      "Fig. 2. An alignment of similar contexts.\n",
      "\n",
      "4 MODULES\n",
      "In the previous section we described the general workﬂow of\n",
      "the MaSTerClass system. Here we provide more details about its\n",
      "modules.\n",
      "\n",
      "4.1 Case-base\n",
      "A case is a unit encapsulating knowledge relevant to a particular\n",
      "experience (Watson and Marir, 1994). It is typically structured into\n",
      "the problem and solution parts. Cases may be represented as feature\n",
      "vectors, frames, objects, predicates, semantic nets, rules, etc. The\n",
      "case representation affects the way in which the similarity between\n",
      "cases can be assessed and the efﬁciency of retrieval. In MaSTerClass,\n",
      "the problem is a term occurrence found in text, while the solution\n",
      "represents a set of classes applicable to the given term. As the context\n",
      "in which a term occurs is often necessary for its classiﬁcation,6 we\n",
      "can view the problem part as a term within a given context. The next\n",
      "question is how the context should be represented, e.g. bag of co-\n",
      "occurring words or terms, text window of a ﬁxed length, sentence,\n",
      "paragraph or document containing the term, lexico-syntactic pattern\n",
      "matching the context, etc. In our approach, we kept as much contex-\n",
      "tual information as possible. First, each context has been annotated\n",
      "with lexical, syntactic and terminological information and treated\n",
      "as a sequence of syntactic and terminological units. Basic syntactic\n",
      "structures (e.g. noun and verb phrases) are recognized through par-\n",
      "tial parsing. Dictionary terms are annotated together with the ones\n",
      "recognized by the NC-value method. Both terms and basic syntactic\n",
      "structures are most often multiword units. By grouping and annot-\n",
      "ating these multiword units the context is structured, i.e. functional\n",
      "relations between consecutive single words are preserved. In addi-\n",
      "tion, the positional information for individual context elements is\n",
      "retained. Second, the relation of a local context and the global dis-\n",
      "course is preserved by deciding to use a pointer to a term occurrence\n",
      "in the corpus rather than a copy of its context. It is a ﬂexible approach,\n",
      "because the structure and length of a context need not be prespeciﬁed.\n",
      "A term is classiﬁed by mapping it to its class and linking it to\n",
      "the knowledge on that class represented by the ontology. Thus, the\n",
      "solution to the problem of classifying a term is a part of the ontology\n",
      "concerned with that particular term.\n",
      "\n",
      "4.2 Similarity measure\n",
      "CBR relies on the hypothesis that similar problems tend to have\n",
      "similar solutions. Therefore, the similarity assessment is a key issue\n",
      "in CBR. It depends on a problem domain and case representation. In\n",
      "the chosen representation, each case corresponds to a term context\n",
      "treated as a sequence of basic syntactic structures and we need to\n",
      "approximately match such sequences. ED has been widely used for\n",
      "approximate string matching, where the distance between identical\n",
      "strings equals zero and increases as the strings get more dissimilar\n",
      "\n",
      "6When classifying biomedical terms, it is by all means necessary to include\n",
      "their context into consideration since (1) terms do not necessarily encode\n",
      "sufﬁcient information to infer their semantic types and (2) the meaning of a\n",
      "term can be modiﬁed by its context.\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "/\n",
      "\n",
      "f\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "with respect to the symbols they contain and the order in which they\n",
      "appear. ED is deﬁned as the minimal cost incurred by the changes\n",
      "needed to transform one string into the other. These changes may\n",
      "include insertion or deletion of a single character, replacement of\n",
      "two characters in the two strings and transposition of two adjacent\n",
      "characters in a single string. The choice of edit operations and their\n",
      "costs depends on a speciﬁc application. ED has been successfully\n",
      "utilized in NLP to deal with alternate spellings, misspellings, the\n",
      "use of upper- and lower-case letters, etc. It has also been used in\n",
      "terminological processing for the recognition of orthographic term\n",
      "variants. For example, Tsuruoka and Tsujii (2004) compared protein\n",
      "names based on their internal properties focusing on orthographic\n",
      "features. Our intention, however, is primarily to explore contextual\n",
      "properties of terms.\n",
      "\n",
      "In this case, it is more convenient to apply ED at the word level\n",
      "rather than the character level, i.e. the character-based ED does\n",
      "not cope well with permutations of words. For instance, judging\n",
      "by the ‘conventional’ ED, stone in kidney is more similar to stone\n",
      "in bladder than kidney stone. Alternatively, approximate string\n",
      "matching can be viewed as the problem of pairing up their words so\n",
      "as to minimize their ED (French et al., 1997). Recently, ED has been\n",
      "applied at the word level to allow different wordings and syntactic\n",
      "mistakes in the phrase-based text search (Navarro et al., 2000). In this\n",
      "approach, ED was simply applied to words as opposed to characters.\n",
      "We, however, developed the SOLD measure by enriching the basic\n",
      "ED approach with both linguistic [relying on part-of-speech (POS)\n",
      "tagging and partial parsing] and biomedical (using an ontology)\n",
      "knowledge (Spasic and Ananiadou, 2005).7\n",
      "\n",
      "Partial parsing is applied to POS-tagged text to group subsequent\n",
      "words into basic syntactic structures. ED applied to blocks of words\n",
      "rather than individual words is ‘forced’ to take syntactic structure\n",
      "(at the phrase level) into account and prevented from artiﬁcially dis-\n",
      "assembling syntagmatic structures by applying edit operations to\n",
      "individual words. By choosing to replace syntactic categories with\n",
      "similar properties at lower costs (e.g. nouns and pronouns), ED can\n",
      "also be used to compare the syntactic structure at the sentence level,\n",
      "i.e. the sentences receiving low ED values are the ones that can be\n",
      "transformed into one another using a small number of low-cost edit\n",
      "operations, implying that their overall syntactic structure is fairly iso-\n",
      "morphic. Furthermore, the cost of deleting (or equivalently inserting)\n",
      "contextual elements depends on their semantic load. For example,\n",
      "terms refer to domain-speciﬁc concepts and as such are the most\n",
      "important means of communicating knowledge in a speciﬁc domain.\n",
      "Therefore, their deletion is the costliest operation, indicating that\n",
      "important information is lost.8\n",
      "\n",
      "7The remainder of Section 4.2 represents a brief report on the similarity\n",
      "measure, which has been extensively described in Spasic and Ananiadou\n",
      "(2005). The reader may wish to read this open-access paper available at\n",
      "http://helix-web.stanford.edu/psb05 before proceeding to Section 4.3.\n",
      "8All types of context elements used and the costs of edit operations involving\n",
      "them are speciﬁed in Spasic and Ananiadou (2005).\n",
      "\n",
      "2751\n",
      "\n",
      "\f",
      "I.Spasic et al.\n",
      "\n",
      "ED usually relies on the exact matches between symbols unless\n",
      "‘wild card’ symbols are allowed. This is unsuitable for word com-\n",
      "parison, because words are inﬂected. Also,\n",
      "the term variation\n",
      "phenomenon can cause synonymous terms not to match. We made\n",
      "the ED approach more ﬂexible with respect to lexical variation. For\n",
      "example, two inﬂected word forms match if both their lexical categor-\n",
      "ies and their base forms are identical. When two terms are compared,\n",
      "information from the ontology is utilized. All semantic classes in\n",
      "UMLS are organized into a hierarchy, which can be used to quantify\n",
      "their similarity. The tree similarity (ts) between two classes C1 and\n",
      "C2 is calculated according to the following formula:\n",
      "\n",
      "ts(C1, C2) = 2 · common(C1, C2)\n",
      "depth(C1) + depth(C2)\n",
      "\n",
      "(1)\n",
      "\n",
      "where common(C1, C2) denotes the number of common classes in\n",
      "the paths between the root and the given classes, and depth(C) is the\n",
      "number of classes in the path connecting the root and the given class.\n",
      "This formula is a derivative of Dice coefﬁcient where ancestor classes\n",
      "are treated as term features. Since the UMLS ontology supports mul-\n",
      "tiple classiﬁcation of terms, we estimate the similarity between two\n",
      "terms as the maximal similarity between their classes. The similarity\n",
      "between two terms quantiﬁed in this manner is used to modify their\n",
      "replacement cost accordingly. The calculation of the replacement\n",
      "cost for two verbs described in the ontology is analogous.\n",
      "\n",
      "The approach used in the ontology-driven component is applicable\n",
      "only to classiﬁed terms and verbs. Currently, biomedical ontologies\n",
      "are inherently incomplete due to the fast-growing number of terms.\n",
      "Therefore, it would be useful to use clues other than the ones expli-\n",
      "citly stated in the ontology in order to extend the semantic comparison\n",
      "to unclassiﬁed terms and verbs. We exploit lexical and morpholo-\n",
      "gical clues as they often indicate semantic similarity. For example,\n",
      "5 alpha-dihydrotestosterone and testosterone are lexically similar,\n",
      "and this fact can be used to infer their semantic similarity. We util-\n",
      "ized the standard ED approach applied at the character level in order\n",
      "to estimate lexical similarity.\n",
      "\n",
      "Finally,\n",
      "\n",
      "the SOLD measure is computed using the standard\n",
      "dynamic programming approach for the calculation of ED (Wagner\n",
      "and Fischer, 1974).\n",
      "\n",
      "4.3 Retrieval\n",
      "Retrieval in CBR serves to improve the efﬁciency of the whole system\n",
      "by allowing for crude (and computationally less expensive) compar-\n",
      "ison of a new case against the ones stored in the case-base. The\n",
      "result is the search space considerably reduced in size. Finer (and\n",
      "costlier) comparison is then performed against the retrieved cases.\n",
      "Ideally, the retrieved cases should be the ones most similar to the\n",
      "new case. However, this is not always straightforward to achieve, so\n",
      "the compromise should be made between two conﬂicting objectives:\n",
      "efﬁciency and precision.\n",
      "\n",
      "We now describe the retrieval approach used in MaSTerClass. Let\n",
      "us recall that, given a non-classiﬁed term occurring in a speciﬁc con-\n",
      "text, we would like to retrieve terms occurring in similar contexts.\n",
      "We previously described how the contextual similarity is assessed\n",
      "by applying the SOLD measure (Spasic and Ananiadou, 2005). We\n",
      "would like to retrieve those contexts that would most probably min-\n",
      "imize the value of this measure. We adopted a heuristic approach\n",
      "exploring the notions of semantic matching and terminological load\n",
      "to achieve this objective.\n",
      "\n",
      "2752\n",
      "\n",
      "Terms tend to co-occur with other terms and verbs denoting spe-\n",
      "ciﬁc relations between them. Terms and domain-speciﬁc verbs also\n",
      "carry the heaviest semantic load. These facts are used to retrieve\n",
      "other similar context (regardless of their structure) by using the terms\n",
      "and verbs found in the context of the unclassiﬁed term. Contexts\n",
      "matching semantically are the ones that share a sufﬁcient number of\n",
      "terminologically relevant elements (i.e. terms and domain-speciﬁc\n",
      "verbs). Semantic matching makes use of terminological information\n",
      "and is ontology-driven. Namely, in UMLS, both terms and verbs are\n",
      "hierarchically organized. These hierarchies are used to quantify the\n",
      "similarity between terms and verbs [Formula (1)]. When retrieving\n",
      "contexts through semantic matching, terms and verbs found in it are\n",
      "used to retrieve their classes (and their close ancestors). The resulting\n",
      "set of classes is then used to retrieve their instances.9 All terms and\n",
      "verbs obtained in this manner form a set of semantically matching\n",
      "tokens. These tokens are then used to query the corpus in order to\n",
      "retrieve semantically similar contexts (i.e. the ones that contain sufﬁ-\n",
      "cient number of semantically matching tokens). Let us exemplify the\n",
      "process of semantic matching by considering the following sentence:\n",
      "\n",
      "Radioinert testosterone (T ) and 5 alphadihydrotestosterone\n",
      "(DHT ) but not androtenedione, progesterone, estradiol-17\n",
      "beta, estrone or cortisol in a 50-fold molar excess inhibited\n",
      "[3H]R1881 binding to the AR in spinal cord, heart, kidney\n",
      "and RT.\n",
      "\n",
      "in which the term testosterone needs to be classiﬁed. Let us sup-\n",
      "pose that the italicized terms have been identiﬁed. In addition, let\n",
      "us assume that the verbs inhibit and bind have been identiﬁed by\n",
      "the tagger. These terms and verbs are used to retrieve other sim-\n",
      "ilar terms and verbs. For example, the term progesterone classiﬁed\n",
      "as a hormone is used to retrieve all other terms from this class, e.g.:\n",
      "thyrotropin-releasing hormone, glucocorticoid, endorphin, etc. Sim-\n",
      "ilarly, the term AR is used to retrieve its expanded form androgen\n",
      "receptor and all other terms from the receptor class, e.g.: thyroid hor-\n",
      "mone receptor beta, thrombomodulin, nuclear receptor, etc. For the\n",
      "verb inhibit the following similar verbs are retrieved: prevent, stop,\n",
      "hinder, repress, impede, etc. All retrieved terms and verbs form a set\n",
      "of semantically matching tokens. These tokens are matched against\n",
      "the corpus to retrieve other sentences containing them, such as:\n",
      "\n",
      "NFI-C does not repress progesterone induction of the MMTV\n",
      "promoter in HeLa cells, suggesting that progesterone induc-\n",
      "tion of the promoter differs mechanistically from glucocorticoid\n",
      "induction.\n",
      "\n",
      "9For efﬁciency reasons (e.g. when classes are too large measured by the\n",
      "number of their instances), a ‘caching’ approach can be used in which each\n",
      "classiﬁed term should be annotated in the corpus with applicable class labels.\n",
      "In this manner, the retrieval of class instances from the ontology is avoided\n",
      "as well as the subsequent complex (measured by the number of matching\n",
      "tokens) queries against the corpus. Instead, ontology is used only to retrieve\n",
      "the class labels and use them to simply query the corpus with the given values\n",
      "of class-label attributes. Furthermore, this attribute can be indexed to speed\n",
      "up the access to relevant terms in the corpus. However, in this approach the\n",
      "corpus should be periodically re-annotated with class information in order to\n",
      "synchronise the corpus with ontology content, which is a step not needed in\n",
      "the original ‘dynamic’ approach.\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "/\n",
      "\n",
      "f\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "\f",
      "For two sentences to be sufﬁciently close with respect to the SOLD\n",
      "measure, it is desirable for them not only to share semantically sim-\n",
      "ilar terms and verbs, but also to have a similar number of them,\n",
      "since their deletion and insertion are the costliest edit operations.\n",
      "In order to take this fact into account during the retrieval process,\n",
      "we introduce the notion of terminological load deﬁned as the num-\n",
      "ber of terms and domain-speciﬁc verbs in a given sentence. Given\n",
      "an input sentence, other sentences with similar terminological load\n",
      "are retrieved. Obviously, the retrieval based on the terminological\n",
      "load does not consider the semantic types of terms and verbs, but\n",
      "simply their number. In order to compensate for this, terminological\n",
      "load is combined with previously described semantic matching, thus\n",
      "retrieving sentences containing a similar number of similar terms and\n",
      "verbs.\n",
      "\n",
      "4.4 Classiﬁcation\n",
      "Once the potentially similar sentences are retrieved from the corpus\n",
      "and their similarity assessed by the SOLD measure, the most similar\n",
      "ones are retained by dynamically setting a distance threshold (t)\n",
      "between the minimal (m) and average (a) value of the SOLD measure\n",
      "for the retrieved sentences: t = m + (a − m) · d, where d (0 ≤ d ≤\n",
      "1)10 is a parameter determining how similar the selected sentences\n",
      "should be. The greater the value of d, the greater the acceptance rate.\n",
      "Multiple sentences are typically selected to perform classiﬁcation.\n",
      "\n",
      "Recall that the SOLD measure is a modiﬁcation of ED, which\n",
      "is based on three types of edit operations: insertion, deletion and\n",
      "replacement. An optimal alignment is a sequence of these opera-\n",
      "tions, whose total cost equals the value of ED. Note that there can\n",
      "be more than one optimal alignment. Optimal alignments can be\n",
      "retrieved from the cost matrix produced when calculating the ED\n",
      "by the dynamic programming method. Given an optimal alignment,\n",
      "two sentences are aligned accordingly. In such an alignment, we are\n",
      "interested in a syntactic element aligned with the considered unclas-\n",
      "siﬁed term. When it is aligned with a classiﬁed term, we hypothesize\n",
      "that they belong to the same class(es).\n",
      "\n",
      "The classiﬁcation results obtained separately for each sentence are\n",
      "combined through a voting procedure. The classes with the majority\n",
      "of votes are suggested as potential classes for the given term. To be\n",
      "precise, a dynamic vote threshold is set as the product of the maximal\n",
      "votes received by a class and the parameter p (0 ≤ p ≤ 1),11 that\n",
      "determines what percentage of the maximal number of votes received\n",
      "is regarded acceptable. If p = 0, then all classes which received\n",
      "a positive number of votes are suggested. On the other extreme, if\n",
      "p = 1, then only the class(es) (>1 if there is a tie) receiving the\n",
      "maximal number of votes are suggested. By using the parameter p\n",
      "we provided support for multiple classiﬁcation. It supports the fact\n",
      "that biomedical concepts often belong to multiple classes depending\n",
      "on the classiﬁcation aspect used. For example, genes can be classi-\n",
      "ﬁed with respect to their function, subcellular location or phenotype\n",
      "[Gene Ontology (http://www.geneontology.org)]. The ontology used\n",
      "in this work includes two major branches in the hierarchy depending\n",
      "on the point of view at a chemical, which can be structural or func-\n",
      "tional. Many terms are classiﬁed in both of these subhierarchies (e.g.\n",
      "many hormones are also classiﬁed as pharmacologic substances).\n",
      "\n",
      "10We have used d = 1.0 in the experiments reported later.\n",
      "11We have used p = 0.9 in the experiments reported later.\n",
      "\n",
      "MaSTerClass\n",
      "\n",
      "Table 1. The classiﬁcation scheme\n",
      "\n",
      "Chemical viewed functionally\n",
      "Pharmacologic Substance\n",
      "\n",
      "Antibiotic\n",
      "\n",
      "Biomedical or dental material\n",
      "Biologically active substance\n",
      "\n",
      "Neuroreactive substance or biogenic amine\n",
      "Hormone\n",
      "Enzyme\n",
      "Vitamin\n",
      "Immunologic factor\n",
      "Receptor\n",
      "\n",
      "Indicator, reagent, or diagnostic aid\n",
      "Hazardous or poisonous substance\n",
      "\n",
      "Fig. 3. A portion of the UMLS Semantic Network: ‘affects’ hierarchy\n",
      "\n",
      "A run-through example summarizing the whole classiﬁcation\n",
      "\n",
      "process is given as Supplementary material.\n",
      "\n",
      "5 EVALUATION\n",
      "\n",
      "5.1 Resources\n",
      "The corpus used as part of the case-base consists of 2072 abstracts\n",
      "on nuclear receptors retrieved from Medline (2004). Each abstract\n",
      "consists of a single title and a number of sentences. The total number\n",
      "of sentences in the corpus (not counting the titles) is 19 449. The\n",
      "initially POS-tagged corpus has been terminologically processed. We\n",
      "have chosen UMLS as the classiﬁcation scheme focusing on a subtree\n",
      "of 13 classes, in which chemicals are classiﬁed according to their\n",
      "functional characteristics (Table 1). All occurrences of 1643 terms\n",
      "contained in the UMLS dictionary have been annotated, resulting in a\n",
      "total of 24 963 annotated term occurrences. In addition, the NC-value\n",
      "method (Frantzi and Ananiadou, 1999) has been applied to recognize\n",
      "terms not listed in the dictionary. A total of 2757 terms have been\n",
      "recognized and annotated in the corpus, resulting in additional 28 935\n",
      "annotated term occurrences. Each sentence has been annotated with\n",
      "its terminological load, the average value being 3.21. In addition,\n",
      "each sentence has been partially parsed in order to recognize syntactic\n",
      "structures of interest. As a result of partial parsing, each sentence is\n",
      "represented as a sequence of blocks, the average number of blocks\n",
      "per sentence being 22.34.\n",
      "\n",
      "In addition to terms, an ontology of verbs was constructed using\n",
      "the part of UMLS Semantic Network that organizes domain-speciﬁc\n",
      "relationships into a hierarchy (Fig. 3). We used the fact that these rela-\n",
      "tionships are expressed by verbs to convert this part of UMLS into\n",
      "an ‘ontology of verbs’. We used the initial hierarchy and the given\n",
      "verbs as a starting point into which we manually placed additional\n",
      "domain-speciﬁc verbs, hand picked from the list of high frequency\n",
      "\n",
      "2753\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "/\n",
      "\n",
      "f\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "\f",
      "I.Spasic et al.\n",
      "\n",
      "Table 2. The evaluation setup\n",
      "\n",
      "Terms\n",
      "\n",
      "Number\n",
      "\n",
      "Percentage\n",
      "(of total)\n",
      "\n",
      "Percentage\n",
      "(of classiﬁed)\n",
      "\n",
      "Training\n",
      "Validation\n",
      "Testing\n",
      "Unclassiﬁed\n",
      "Total\n",
      "\n",
      "18 236\n",
      "2405\n",
      "2838\n",
      "30 419\n",
      "53 898\n",
      "\n",
      "33.83\n",
      "4.46\n",
      "5.27\n",
      "56.44\n",
      "100.00\n",
      "\n",
      "77.67\n",
      "10.24\n",
      "12.09\n",
      "—\n",
      "—\n",
      "\n",
      "verbs extracted automatically from the corpus. The resulting onto-\n",
      "logy covers 99 inﬁnitive forms of verbs distributed across 23 classes.\n",
      "A total of 55 581 verb occurrences have been recognized out of which\n",
      "14 560 have been treated as domain speciﬁc.\n",
      "\n",
      "5.2 Evaluation setup\n",
      "The classiﬁcation experiments were performed only for terms from\n",
      "the corpus that are classiﬁed in the ontology in order to automatic-\n",
      "ally evaluate the classiﬁcation results. The corresponding concepts\n",
      "(not terms) were divided randomly into three sets (using the approx-\n",
      "imate ratio 15:15:70) and mapped into the sets of terms to be used\n",
      "for validation, testing and training respectively. Table 2 summarizes\n",
      "the distribution of term occurrences across the training, validation,\n",
      "testing and non-classiﬁed sets of terms.\n",
      "\n",
      "5.3 Evaluation measures\n",
      "We used a standard set of evaluation measures to quantify the results\n",
      "of the classiﬁcation experiments. These measures include precision,\n",
      "recall and F -measure. The precision and recall are calculated for\n",
      "each class separately according to the following two formulas:\n",
      "\n",
      "P = A/(A + B)\n",
      "R = A/(A + C)\n",
      "\n",
      "(2)\n",
      "\n",
      "(3)\n",
      "\n",
      "where A is the number of true positives (the number of times the\n",
      "class was correctly predicted), B is the number of false positives\n",
      "(the number of times the class was incorrectly predicted) and C is\n",
      "the number of false negatives (the number of times the class was\n",
      "incorrectly not predicted). The precision and recall for all classes\n",
      "collectively can be calculated through macro-averaging or micro-\n",
      "averaging. The macro-averaged precision and recall are calculated by\n",
      "averaging the precision and recall obtained for each class separately\n",
      "by Formulas (2) and (3). Alternatively, when calculating the micro-\n",
      "averaged values, the numbers of true positives, false positives and\n",
      "false negatives obtained for each class separately are summed up\n",
      "to obtain the corresponding overall numbers. The micro-averaged\n",
      "precision and recall then combine these values as before [Formulas\n",
      "(2) and (3)]. In all cases, the F -measure is calculated as the harmonic\n",
      "mean of precision and recall: F = 2 · P · R/(P + R).\n",
      "\n",
      "The problem of judging the classiﬁcation performance based on\n",
      "the described measures is that they only consider whether the pre-\n",
      "dicted class is correct or not, and conversely whether the actual\n",
      "class is predicted or not. This may be too crude for extensive clas-\n",
      "siﬁcation schemes, because the probability of a correct prediction\n",
      "decreases as the number of classes increases. In such cases, a simple\n",
      "method that maps every instance to the largest class could easily\n",
      "\n",
      "2754\n",
      "\n",
      "‘outperform’ other, more subtle classiﬁcation methods, since the\n",
      "number of correctly classiﬁed instances would be large as well. How-\n",
      "ever, the usability of such ‘better’ results is seriously reduced, since\n",
      "they offer no information gain. However, a method that often fails to\n",
      "make correct predictions, but consistently makes predictions ‘close’\n",
      "to the correct classes, can be more useful because it focuses on the\n",
      "correct class neighbourhood (as opposed to a single correct class).\n",
      "\n",
      "(cid:1)\n",
      "\n",
      "Therefore, we introduce a concept of graded precision and recall,\n",
      "where we measure the distance (or similarity) between the predicted\n",
      "and actual classes rather than their equality. Since the classiﬁcation\n",
      "scheme used is hierarchically organized, we used the tree similarity\n",
      "measure [Formula (1)] to modify the numerators in Formulas (2) and\n",
      "(3). Previously, the numerator A was used to count true positives for\n",
      "each class C in the following manner: A =\n",
      "at , where t enumerates\n",
      "the testing term occurrences: at is 1 if C ∈ predicted(t) ∩ actual(t)\n",
      "and 0 otherwise, where predicted(t) and actual(t) denote the sets of\n",
      "predicted and actual classes, respectively for the given term t. In\n",
      "our evaluation approach, we want to measure the distance between\n",
      "the predicted and actual classes rather then comparing them binary.\n",
      "For example, given a class C, for each testing term occurrence t,\n",
      "we compare the given class with the term’s actual classes looking\n",
      "for the minimal distance: aP\n",
      "is calculated as the maximal value of\n",
      "t\n",
      "ts(C, CA) for all classes CA ∈ actual(t) if C ∈ predicted(t) and 0\n",
      "otherwise. In this manner we measure the degree of incorrectness.\n",
      "Similarly, we compare the given class with all predicted classes for\n",
      "each term t looking for the minimal distance in order to estimate the\n",
      "recall: aR\n",
      "is assigned the maximal value of ts(C, CP) for all classes\n",
      "t\n",
      "CP ∈ predicted(t) if C ∈ actual(t) and 0 otherwise. We measure by\n",
      "how much the system missed a correct class. Finally, the numerators\n",
      "ap\n",
      "in Formulas (2) and (3) are modiﬁed as follows: AP =\n",
      "t and\n",
      "AR =\n",
      "aR\n",
      "t , giving the formulas for the graded precision and recall:\n",
      "GP = AP /(A + B) and GR = AR/(A + C). Finally, the values\n",
      "obtained for individual classes are combined as before to calculate\n",
      "macro- and micro-averaged values.\n",
      "\n",
      "(cid:1)\n",
      "\n",
      "(cid:1)\n",
      "\n",
      "5.4 Baseline methods\n",
      "We compare the results of our experiments with those obtained by six\n",
      "baseline methods. We relied on methods commonly used to evaluate\n",
      "classiﬁcation results, such as random classiﬁer and the method that\n",
      "assigns the largest class to all objects of classiﬁcation. In addition, we\n",
      "implemented a naive Bayes classiﬁer and a rule-based classiﬁcation\n",
      "method.\n",
      "\n",
      "The ﬁrst baseline method (B1) assigns a random class to each\n",
      "term occurrence. The following three methods (B2–B4) map each\n",
      "term occurrence to the largest class measured by the number of its\n",
      "concepts, terms and term occurrences respectively.\n",
      "\n",
      "A naive Bayes classiﬁer (whose goal is to maximize the condi-\n",
      "tional probability of a given term being assigned to a speciﬁc class\n",
      "based on the features used to represent the term) was used as the\n",
      "ﬁfth baseline method (B5). Each term is represented as a bag of\n",
      "co-occurring words, i.e. all single words occurring with the given\n",
      "term within a sentence. The aforementioned conditional probability\n",
      "is then estimated as the product of the class probability (estimated\n",
      "as the ratio between the number of all terms labelled with the given\n",
      "class and the total number of terms) and the conditional probabil-\n",
      "ities of features given the class (estimated as the ratio between the\n",
      "number of times a given single word co-occurs with terms from\n",
      "the given class and the number of all single words co-occurring with\n",
      "terms from the given class). Finally, we used rule-based classiﬁcation\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "/\n",
      "\n",
      "f\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "\f",
      "Table 3. A sample of term classiﬁcation rules\n",
      "\n",
      "Table 4. The summary of experiments performed\n",
      "\n",
      "if\n",
      "then\n",
      "if\n",
      "\n",
      "then\n",
      "if\n",
      "then\n",
      "\n",
      "Term contains a word starting with preﬁx ‘immun-’ or ‘anti-’\n",
      "class is ‘Immunologic Factor’\n",
      "Term contains any of the words ‘toxin’, ‘insecticid’ or ‘pesticid’ or\n",
      "a word starting with preﬁx ‘carcin-’, ‘cancer-’ or ‘radioactiv-’\n",
      "\n",
      "class is ‘Hazardous or Poisonous Substance’\n",
      "Term contains a word ending with sufﬁx ‘-cyclin’ or ‘-mycin’\n",
      "class is ‘Antibiotic’\n",
      "\n",
      "(Table 3) similar to that of Fukuda et al. (1998) as the sixth baseline\n",
      "method (B6).\n",
      "\n",
      "5.5 Experiments\n",
      "We conducted a series of three experiments: E1, the CBR classiﬁc-\n",
      "ation method used in MaSTerClass; E2, the same method supplied\n",
      "with more extensive biomedical knowledge; E3, the CBR method\n",
      "combined with classiﬁcation rules exploiting the internal term char-\n",
      "acteristics. The hypothesis behind the experiment E2 is that the\n",
      "knowledge contained in the ontology may not be equally discrim-\n",
      "inative for all classes. In other words, precision and recall for\n",
      "individual classes may depend on the completeness of the onto-\n",
      "logy used. Broader and more ﬁne-grained ontologies should have\n",
      "higher discriminative power. For example,\n",
      "in the classiﬁcation\n",
      "scheme used (Table 1), receptors are expected to co-occur with hor-\n",
      "mones and vitamins (both classes being present in the classiﬁcation\n",
      "scheme), whereas hazardous or poisonous substances are expected\n",
      "to co-occur with terms denoting diseases, syndromes, poisoning, etc.\n",
      "(not covered by the classiﬁcation scheme). To test this hypothesis,\n",
      "we expanded the classiﬁcation scheme with other classes found in\n",
      "UMLS. The unclassiﬁed term occurrences were matched against the\n",
      "whole UMLS ontology and the retrieved information incorporated\n",
      "into the smaller ontology. The reason we did not retag the corpus\n",
      "with all terms found in the UMLS, but instead we only classiﬁed\n",
      "already annotated unclassiﬁed terms, is that we wanted to examine\n",
      "the effects of the classiﬁcation information being attached to terms\n",
      "against the absence of this information. A total of 2757 originally\n",
      "unclassiﬁed terms were identiﬁed in the corpus, out of which 547\n",
      "were found in the UMLS. These terms resulted in 186 concepts,\n",
      "1329 term variants and 53 classes being added to the core ontology\n",
      "used for the experiments. Based on the newly available classiﬁcation\n",
      "information, 6774 term occurrences in the corpus were additionally\n",
      "annotated as classiﬁed.\n",
      "\n",
      "With the lack of strict naming conventions in biomedicine reﬂect-\n",
      "ing particular functional properties of terms, context may often be\n",
      "the only clue to their meaning. Although there are no general termin-\n",
      "ological standards which would help discriminate between speciﬁc\n",
      "classes of terms in biomedicine, there are naming conventions for\n",
      "some types of concepts in the domain, e.g. genes, alleles and pro-\n",
      "teins (Oliver et al., 2002). These conventions are only guidelines and\n",
      "as such do not impose restrictions to experts. Still, when a concept\n",
      "is named by a term that is in accordance with the provided conven-\n",
      "tions, these clues should be exploited rather than be neglected in\n",
      "favour of contextual clues. For example, the sufﬁx -ase can be used\n",
      "to identify terms denoting enzymes with high precision. In an attempt\n",
      "to investigate the effects of internal term characteristics, we analysed\n",
      "the features of terms contained in the ontology and tried to generalize\n",
      "\n",
      "MaSTerClass\n",
      "\n",
      "Experiment\n",
      "\n",
      "Description\n",
      "\n",
      "E1\n",
      "E2\n",
      "E3\n",
      "B1\n",
      "B2\n",
      "B3\n",
      "B4\n",
      "B5\n",
      "B6\n",
      "\n",
      "Core (case-based reasoning)\n",
      "Core + extended general knowledge\n",
      "Core + rules\n",
      "Random\n",
      "Majority by the number of concepts\n",
      "Majority by the number of terms\n",
      "Majority by the number of term occurrences\n",
      "Naive Bayes\n",
      "Rule-based\n",
      "\n",
      "some of them into classiﬁcation rules (Table 3). Table 4 summarizes\n",
      "the experiments performed.\n",
      "\n",
      "5.6 Results\n",
      "The experimental results are shown in Table 5, in which P , R and\n",
      "F denote precision, recall and F -measure, while GP, GR and GF\n",
      "stand for the corresponding graded measures. Let us ﬁrst discuss\n",
      "the hypothesis about the knowledge contained in the ontology not\n",
      "being equally discriminative to all classes by comparing the results\n",
      "given for experiments E1 and E2. In experiment E2, an improve-\n",
      "ment has been noticed in the majority of the evaluation measures\n",
      "used. The most signiﬁcant improvement is that of macro-averaged\n",
      "precision due to the precision evening out across the classes. The\n",
      "distribution of true positives changed because the expanded onto-\n",
      "logy helped to improve the results for certain classes, whereas they\n",
      "were downgraded for others. The reason for deterioration is that the\n",
      "classes from the old ontology were moved lower down in the new\n",
      "ontology with respect to the root, thus automatically appearing more\n",
      "similar [Formula (1)]. The new tree similarity values consequently\n",
      "inﬂuenced the changes in the results of approximate context match-\n",
      "ing. However, the positive impact of using the expanded ontology\n",
      "outbalanced the negative impact, thus resulting in a better overall\n",
      "performance. The expanded ontology contained 66 classes, which is\n",
      "<50% of 135 classes supported in UMLS. In addition, we did not\n",
      "use all terms from the 66 classes mentioned, but only those already\n",
      "annotated in the corpus. We conclude that the best results would\n",
      "be achieved with an ontology that covers all aspects of the domain.\n",
      "In the experiment E3, the core method has been combined with a\n",
      "rule-based approach exploiting internal term features. A signiﬁcant\n",
      "improvement has been noticed in all evaluation measures used, sug-\n",
      "gesting that internal features can contribute signiﬁcantly to better\n",
      "classiﬁcation performance.\n",
      "\n",
      "Let us now compare the results of our experiments with those\n",
      "achieved by the baseline methods. In the majority of cases, our\n",
      "method outperformed the baseline methods. The signiﬁcant improve-\n",
      "ment in comparison to the random classiﬁer suggests that our method\n",
      "represents a reasonably strong classiﬁcation method. Similarly, our\n",
      "core method outperforms the ‘majority’ classiﬁcation methods on\n",
      "all micro-averaged evaluation measures. As for the macro-averaged\n",
      "evaluation measures, the baseline methods appear to have ‘better’\n",
      "precision. However, a classiﬁcation method that assigns a ﬁxed class\n",
      "to all objects of classiﬁcation would always have a high macro-\n",
      "averaged precision when applied against a classiﬁcation scheme with\n",
      "\n",
      "2755\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "/\n",
      "\n",
      "f\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "\f",
      "I.Spasic et al.\n",
      "\n",
      "Table 5. Experimental results\n",
      "\n",
      "Experiment Macro-averaged\n",
      "R\n",
      "\n",
      "P\n",
      "\n",
      "F\n",
      "\n",
      "GP\n",
      "\n",
      "GR\n",
      "\n",
      "GF\n",
      "\n",
      "F\n",
      "\n",
      "GP\n",
      "\n",
      "GR\n",
      "\n",
      "GF\n",
      "\n",
      "Micro-averaged\n",
      "R\n",
      "P\n",
      "\n",
      "E1\n",
      "E2\n",
      "E3\n",
      "B1\n",
      "B2\n",
      "B3\n",
      "B4\n",
      "B5\n",
      "B6\n",
      "\n",
      "45.93\n",
      "60.50\n",
      "63.89\n",
      "10.75\n",
      "94.97\n",
      "92.31\n",
      "94.97\n",
      "54.22\n",
      "93.56\n",
      "\n",
      "13.16\n",
      "19.74\n",
      "35.48\n",
      "6.85\n",
      "7.69\n",
      "7.69\n",
      "7.69\n",
      "10.31\n",
      "23.85\n",
      "\n",
      "20.46\n",
      "29.77\n",
      "45.62\n",
      "8.37\n",
      "14.23\n",
      "14.20\n",
      "14.23\n",
      "17.33\n",
      "38.01\n",
      "\n",
      "82.21\n",
      "86.75\n",
      "88.09\n",
      "64.19\n",
      "97.19\n",
      "97.57\n",
      "97.19\n",
      "82.29\n",
      "96.46\n",
      "\n",
      "62.81\n",
      "66.13\n",
      "71.00\n",
      "56.77\n",
      "52.82\n",
      "58.21\n",
      "52.82\n",
      "40.40\n",
      "27.36\n",
      "\n",
      "71.21\n",
      "75.05\n",
      "78.63\n",
      "60.25\n",
      "68.44\n",
      "72.92\n",
      "68.44\n",
      "54.19\n",
      "42.63\n",
      "\n",
      "42.90\n",
      "43.38\n",
      "67.96\n",
      "10.60\n",
      "34.67\n",
      "0.05\n",
      "34.67\n",
      "41.95\n",
      "98.94\n",
      "\n",
      "32.07\n",
      "32.65\n",
      "50.90\n",
      "7.77\n",
      "25.43\n",
      "0.03\n",
      "25.43\n",
      "18.12\n",
      "29.58\n",
      "\n",
      "36.70\n",
      "37.25\n",
      "58.21\n",
      "8.97\n",
      "29.34\n",
      "0.04\n",
      "29.34\n",
      "25.31\n",
      "45.54\n",
      "\n",
      "80.61\n",
      "81.00\n",
      "89.94\n",
      "63.99\n",
      "63.46\n",
      "68.39\n",
      "63.46\n",
      "83.11\n",
      "99.57\n",
      "\n",
      "67.44\n",
      "67.99\n",
      "75.82\n",
      "58.03\n",
      "57.39\n",
      "60.92\n",
      "57.39\n",
      "43.14\n",
      "31.55\n",
      "\n",
      "73.43\n",
      "73.92\n",
      "82.28\n",
      "60.86\n",
      "60.27\n",
      "64.44\n",
      "60.27\n",
      "56.80\n",
      "47.92\n",
      "\n",
      "multiple classes; i.e. the class precision would be 100% for all classes\n",
      "other than the chosen ﬁxed class, resulting in the average class pre-\n",
      "cision getting closer to 100% with the higher number of classes. In\n",
      "addition, the averaged precision is even higher when the ﬁxed class is\n",
      "a majority class, because its class precision would be higher. In this\n",
      "case, the macro-averaged precision provides misleading estimation\n",
      "of the quality of classiﬁcation, which is made obvious by low macro-\n",
      "averaged recall values. In general, a reliable conclusion about the\n",
      "classiﬁcation quality cannot be reached by looking at a single eval-\n",
      "uation measure. Instead, as many evaluation measures as possible\n",
      "should be taken into account in order to provide a fuller insight.\n",
      "\n",
      "Furthermore, the micro-averaged precision of our method is sim-\n",
      "ilar to that of the naive Bayes classiﬁer. Although our method did not\n",
      "signiﬁcantly outperform the precision of this baseline method, this\n",
      "fact is still taken as a positive feature of our classiﬁcation approach,\n",
      "because it is comparable with the method which maximizes the prob-\n",
      "ability of a correct prediction. However, our method signiﬁcantly\n",
      "outperforms the recall (graded recall in particular) of the naive Bayes\n",
      "classiﬁer, which results in better overall performance estimated by\n",
      "the F -measure. The only measure where the naive Bayes classiﬁer\n",
      "signiﬁcantly outperformed our method is the macro-averaged preci-\n",
      "sion. This happened because the naive Bayes classiﬁer concentrated\n",
      "on the most probable classes (in general and not for speciﬁc term\n",
      "occurrence alone), whereas the least probable classes were rarely\n",
      "suggested. Therefore, the least probable classes were seldom used\n",
      "to produce incorrect classiﬁcations, thus having high class precision.\n",
      "This reﬂected well on the macro-averaged precision. Again, a single\n",
      "evaluation measure cannot be used to fairly judge a classiﬁcation\n",
      "method. For example, in this case, other evaluation measures imply\n",
      "the overall poorer quality compared with our classiﬁcation method.\n",
      "Finally, let us compare our approach with the rule-based method.\n",
      "Our method outperformed the given baseline on half of the evaluation\n",
      "measures. Not surprisingly, the precision of rule-based classiﬁca-\n",
      "tion is extremely high. This is a general characteristic of rule-based\n",
      "classiﬁcation. However, the opposition between precision and recall\n",
      "is particularly apparent in such systems. Namely, more rules typ-\n",
      "ically increase recall due to higher coverage, but decrease the\n",
      "precision at the same time. In general,\n",
      "the rule-based method\n",
      "provides better precision, while our method provides better recall.\n",
      "The beneﬁts of these two complementary features are exploited in a\n",
      "hybrid approach (E3), which signiﬁcantly improved the precision\n",
      "of our CBR method, while signiﬁcantly improving the recall of\n",
      "\n",
      "2756\n",
      "\n",
      "the rule-based method. The F -measure (in all four forms) for the\n",
      "combined method signiﬁcantly enhances the F -measure for both\n",
      "methods used separately.\n",
      "\n",
      "Based on the comparison with the six baseline methods, we\n",
      "conclude that our method provides a strong classiﬁcation model.\n",
      "However, there is room for further improvement. The best results\n",
      "have been achieved with additional knowledge used, including the\n",
      "expansion of the original ontology and the use of rules generaliz-\n",
      "ing internal term characteristics into the corresponding classes. The\n",
      "results substantiate the superiority of the combined method in com-\n",
      "parison to the given baseline methods. However, further evaluation\n",
      "is needed with more diverse ontologies and large-size corpora.\n",
      "\n",
      "6 DISCUSSION AND CONCLUSIONS\n",
      "We explored the use of CBR for the burning problem of term clas-\n",
      "siﬁcation in biomedicine. In particular, we described MaSTerClass\n",
      "as a speciﬁc implementation for this problem, which classiﬁes indi-\n",
      "vidual term occurrences by learning how to locate other similar cases\n",
      "and extract linguistic and biomedical information necessary to per-\n",
      "form classiﬁcation from these cases. We demonstrated through a set\n",
      "of experiments that an effective and efﬁcient ML approach can be\n",
      "developed and successfully employed for the given problem. We\n",
      "moved away from the existing classiﬁcation approaches in several\n",
      "aspects. First, most of the existing approaches do not utilize high\n",
      "degree of biomedical and linguistic knowledge. Most often, they\n",
      "target speciﬁc classes by exploiting surface features (such as ortho-\n",
      "graphic or lexical) typical of these classes. The main problem in\n",
      "such approaches is the obscurity of discriminative features. In our\n",
      "approach, we make use of linguistic and domain-speciﬁc features,\n",
      "as both are necessary for reliable classiﬁcation. The linguistic know-\n",
      "ledge is applied to acquire syntactic features of term contexts. In\n",
      "addition, our system efﬁciently utilizes explicit and extensive bio-\n",
      "medical knowledge. While other systems may explicitly encode a\n",
      "certain degree of biomedical knowledge, they usually do so through\n",
      "a set of rules. Such knowledge representation approaches are tar-\n",
      "geted at speciﬁc tasks and classes and as such have limited generality\n",
      "and applicability. In our approach, the knowledge is represented by\n",
      "an ontology which comprises information about concepts (together\n",
      "with terms representing them), their classes and mutual relations.\n",
      "Unlike rules, ontologies can be used for various applications by both\n",
      "human users and computers. The effort needed to utilize an existing\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "/\n",
      "\n",
      "f\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "\f",
      "biomedical ontology in our system is considerably lower than that\n",
      "required to engineer satisfactory classiﬁcation rules, which makes\n",
      "our system easily portable between different tasks and subdomains.\n",
      "As opposed to the existing term classiﬁcation systems, rather than\n",
      "generalizing the background knowledge (both biomedical and lin-\n",
      "guistic) into a complex set of formal rules guiding the classiﬁcation\n",
      "process, we opted to perform generalization as part of the classiﬁc-\n",
      "ation process by relating the unclassiﬁed term occurrences together\n",
      "with their contexts to classiﬁed terms occurring in similar contexts.\n",
      "A ﬂexible distance measure has been developed as a way of relating\n",
      "unclassiﬁed to relevant classiﬁed terms, which combines linguistic\n",
      "and domain-speciﬁc features. The ﬂexibility of the method reﬂects\n",
      "in the fact that some features can be discarded, whereas others can\n",
      "be changed in an ad hoc manner to suit speciﬁc circumstances.\n",
      "\n",
      "However, there is room for further improvement of the similarity\n",
      "measure in order to tackle the problem of discrepancy between the\n",
      "knowledge described in the ontology and that found in the literature.\n",
      "Currently, lexical similarity based on ED is used as an alternative\n",
      "to semantic comparison of ‘unknown’ terms, but it is not always\n",
      "appropriate, e.g. when very short terms as potential acronyms (2–4\n",
      "characters) are compared with longer terms, in which case the ED\n",
      "would result in high values that do not reﬂect well the semantic sim-\n",
      "ilarity between the terms involved. Therefore, expanding acronyms\n",
      "to their full forms could improve the overall similarity for some\n",
      "cases. However, acronym matching need to be handled with spe-\n",
      "cial caution, since they are known to be highly ambiguous (e.g.\n",
      "AR could be expanded to any of the following terms: androgen\n",
      "receptor, amphiregulin, acyclic retinoid, agonist-receptor, adrener-\n",
      "gic receptor, etc.). Their polysemy can be tackled by quantifying the\n",
      "match between an acronym and the expanded form with the probab-\n",
      "ility of their match estimated from the number of possible expanded\n",
      "forms through acronym acquisition and term variant management\n",
      "(Nenadic et al., 2002). In addition, a more general approach to the\n",
      "problems caused by synonymy and polysemy will be used in future\n",
      "versions of the system, i.e. the latent semantic analysis will be used\n",
      "to infer semantic properties of terms by statistically estimating the\n",
      "contextual usage substitutability of terms (Deerwester et al., 1990).\n",
      "Furthermore, the presented approach is context-sensitive and as\n",
      "such can readily be utilized for disambiguation of biomedical terms\n",
      "(e.g. to distinguish between homonymous genes and proteins they\n",
      "encode). In that sense, our method is more general than other term\n",
      "classiﬁcation approaches. In our approach we classify speciﬁc occur-\n",
      "rences rather than generic terms. Nonetheless, terms in general can\n",
      "still be classiﬁed by collecting classiﬁcation information obtained\n",
      "for their occurrences. Other approaches either do not exploit the\n",
      "context at all (i.e. rely only on the internal term features) or process\n",
      "them collectively rather than focusing on a speciﬁc term occurrence\n",
      "and its context. The former approach cannot be generally used for\n",
      "disambiguation, because the appropriate interpretation of an ambigu-\n",
      "ous term can be inferred only from its context. Similarly, the latter\n",
      "approach cannot be used for term disambiguation unless the contexts\n",
      "are clustered so as to reﬂect speciﬁc aspects of terms used in them,\n",
      "which requires additional processing.\n",
      "\n",
      "Another advantage of the MaSTerClass system is the ability to\n",
      "learn by storing newly solved classiﬁcation problems for future use,\n",
      "hence gradually improving its competence. The suggested term clas-\n",
      "siﬁcation approach is inductive in its nature, thus bearing strong\n",
      "resemblance to the human acquisition of language, who are believed\n",
      "not to acquire their native languages through rules, but rather to learn\n",
      "\n",
      "MaSTerClass\n",
      "\n",
      "from examples by performing analogical reasoning. Moreover, the\n",
      "users are expected to embrace the CBR system more readily, largely\n",
      "due to the fact that similar cases readily lend an explanation for a par-\n",
      "ticular choice of solution by presenting a context in which a similar\n",
      "solution produced satisfactory results. In particular, the validation of\n",
      "the classiﬁcation results and their incorporation into an ontology are\n",
      "made easier, because the human curator can be offered an explan-\n",
      "ation by presenting the new term, its context, together with other\n",
      "similar terms in similar contexts.\n",
      "\n",
      "ACKNOWLEDGEMENTS\n",
      "I.S. gratefully acknowledges support from the Overseas Research\n",
      "Students Award Scheme (ORSAS), UK. S.A. is supported by the\n",
      "JISC-funded National Centre for Text Mining (NaCTeM), UK. All\n",
      "authors express their gratitude to Daiwa Foundation for enabling\n",
      "their scientiﬁc collaboration under the Daiwa Adrian Prize scheme.\n",
      "\n",
      "REFERENCES\n",
      "\n",
      "Aamodt,A. (1995) Knowledge acquisition and learning from experience—the role of\n",
      "case-speciﬁc knowledge. In Tecuci,G. and Kodratoff,Y. (eds), Machine Learning\n",
      "and Knowledge Acquisition; Integrated Approaches. Academic Press, New York,\n",
      "pp. 197–245.\n",
      "\n",
      "Aha,D. (1998) The omnipresence of case-based reasoning in science and application.\n",
      "\n",
      "Knowledge-Based Systems, 11, 261–273.\n",
      "\n",
      "Collier,N. et al. (2001) Automatic acquisition and classiﬁcation of terminology using a\n",
      "\n",
      "tagged corpus in the molecular biology domain. J. Terminol., 7, 239–257.\n",
      "\n",
      "Collier,N. and Takeuchi,K. (2004) Comparison of character-level and part of speech\n",
      "features for name recognition in biomedical texts. J. Biomed. Inform., 37, 423–435.\n",
      "Deerwester,S. et al. (1990) Indexing by latent semantic analysis. J. Soc. Inform. Sci., 41,\n",
      "\n",
      "391–407.\n",
      "\n",
      "Frantzi,K. and Ananiadou,S. (1999) The C-value/NC-value domain independent method\n",
      "\n",
      "for multiword term extraction. J. Nat. Lang. Process., 6, 145–180.\n",
      "\n",
      "French,J., Powell,A. and Schulman,E. (1997) Applications of approximate word match-\n",
      "ing in information retrieval. In Golshani,F. and Makki,K. (eds), Proceedings of the 6th\n",
      "International Conference on Knowledge and Information Management, Los Angeles,\n",
      "CA, ACM, New York, pp. 9–15.\n",
      "\n",
      "Fukuda,K., Tsunoda,T., Tamura,A. and Takagi,T. (1998) Toward information extraction:\n",
      "identifying protein. In Altman,R. Keith,D.K. and Hunter,L. (eds), Proceedings of\n",
      "PSB, Hawaii, USA, World Scientiﬁc Publishing Company, Singapore, pp. 705–716.\n",
      "Gierl,L., Bull,M. and Schmidt,R. (1998) CBR in medicine. In Lenz,M. Bartsch-Spörl,B.,\n",
      "Burkhard,H.-D. and Wess,S. (eds), Case-Based Reasoning Technology: From\n",
      "Foundations to Applications. LNCS 1400, Springer-Verlag, Berlin, pp. 273–298.\n",
      "Globig,C. et al. (1997) On case-based learnability of languages. New Generation\n",
      "\n",
      "Comput., 15, 39–83.\n",
      "\n",
      "Gross,M. (1997) The construction of local grammars. In Roche,E. and Schabes,Y. (eds),\n",
      "\n",
      "Finite State Language Processing. MIT Press, CA, pp. 329–352.\n",
      "\n",
      "Hatzivassiloglou,V. et al. (2001) Disambiguating proteins, genes and RNA in text: a\n",
      "\n",
      "machine learning approach. Bioinformatics, 1, 97–106.\n",
      "\n",
      "Jurisica,I. and Glasgow,J. (2004) Applications of case-based reasoning in molecular\n",
      "\n",
      "biology. AI Magazine, 25, 85–95.\n",
      "\n",
      "Kazama,J., Makino,T., Ohta,Y. and Tsujii,J. (2002) Tuning support vector machines for\n",
      "biomedical named entity recognition. In Johnson,S. (ed.), Proceedings of the ACL\n",
      "Workshop on Natural Language Processing in the Biomedical Domain, Philadelphia,\n",
      "PA, Morgan Kaufmann, pp. 1–8.\n",
      "\n",
      "Kolodner,J. (1993) Case-Based Reasoning. Morgan Kaufmann.\n",
      "Leake,D. (1996) Case-based reasoning: the present and future. In Leake,D. (ed), Case-\n",
      "Based Reasoning: Experiences, Lessons, and Future Directions: AAAI Press/MIT\n",
      "Press, CA.\n",
      "\n",
      "Lee,K., et al. (2004) Biomedical named entity recognition using two-phase model based\n",
      "\n",
      "on SVMs. J. Biomed. Inform., 37, 436–447.\n",
      "\n",
      "Macura,R.T. and Macura,K. (1997) Case-based reasoning: opportunities and applica-\n",
      "\n",
      "tions in health care. Artif. Intell. Med., 9, 1–4.\n",
      "\n",
      "MEDLINE (2004).\n",
      "Nakagawa,H. and Mori,T. (1998) Nested collocation and compound noun for term recog-\n",
      "nition. Proceedings of the 1st Workshop on Computational Terminology, Montreal,\n",
      "Canada, pp. 64–70.\n",
      "\n",
      "2757\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "/\n",
      "\n",
      "f\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "\f",
      "I.Spasic et al.\n",
      "\n",
      "Nakagawa,H. and Mori,T. (2003) Automatic term recognition based on statistics of\n",
      "\n",
      "compound nouns and their components. Terminology, 9, 201–219.\n",
      "\n",
      "Narayanaswamy,M., Ravikumar,K.E. and Vijay-Shanker,K. (2003) A biological named\n",
      "entity recognizer. In Altman,R. et al. (eds), Proceedings of PSB, Hawaii, USA, World\n",
      "Scientiﬁc Publishing Company, Singapore, pp. 427–438.\n",
      "\n",
      "Navarro,G. (2001) A guided tour to approximate string matching. ACM Comput. Survey.,\n",
      "\n",
      "Navarro,G., et al. (2000) Adding compression to block addressing inverted indexes.\n",
      "\n",
      "33, 31–88.\n",
      "\n",
      "Information Retrieval, 3, 49–77.\n",
      "\n",
      "Syst. Trend. Controversies, 17, 76–80.\n",
      "\n",
      "Nedellec,C. (2002) Bibliographical information extraction in genomics. IEEE Intelligent\n",
      "\n",
      "Nenadic,G., Spasic,I. and Ananiadou,S. (2002) Automatic acronym acquisition\n",
      "and management within domain-speciﬁc texts. Proceedings of\n",
      "the 3rd Inter-\n",
      "national Conference on Language, Resources and Evaluation, Las Palmas, Spain,\n",
      "pp. 2155–2162.\n",
      "\n",
      "Nobata,C., Collier,N. and Tsujii,J. (2000) Automatic term identiﬁcation and classiﬁca-\n",
      "tion in biology texts. Proceedings of the Natural Language Paciﬁc Rim Symposium,\n",
      "Beijing, China, pp. 369–374.\n",
      "\n",
      "Oliver,D., Rubin,D., Stuart,J., Hewett,M., Klein,T. and Altman,R. (2002) Ontology\n",
      "development for a pharmacogenetics knowledge base. In Altman,R. Dunker,A.K.,\n",
      "\n",
      "Hunter,L. and Klein,T.E. (eds), Proceedings of PSB, Hawaii, USA, World Scientiﬁc\n",
      "Publishing Company, Singapore, pp. 65–76.\n",
      "\n",
      "Schmidt,R. et al. (2001) Cased-based reasoning for medical knowledge-based systems.\n",
      "\n",
      "Int. J. Med. Inform., 64, 355–367.\n",
      "\n",
      "Spasic,I. and Ananiadou,S. (2005) A ﬂexible measure of contextual similarity for bio-\n",
      "medical terms. In Altman,R. Jung,T.A., Klein,T.E., Dunker,A.K. and Hunter,L. (eds),\n",
      "Proceedings of PSB, Lihue, Hawaii, USA, World Scientiﬁc Publishing Company,\n",
      "Singapore, pp. 197–208.\n",
      "\n",
      "Stapley,B., Kelley,L.\n",
      "\n",
      "and Sternberg,M.\n",
      "\n",
      "(2002) Predicting the\n",
      "\n",
      "from text using support vector machines.\n",
      "\n",
      "location of proteins\n",
      "man,R. Dunker,A.K., Hunter,L.\n",
      "PSB, Hawaii, USA, World Scientiﬁc Publishing Company,\n",
      "pp. 374–385.\n",
      "\n",
      "and Klein,T.E.\n",
      "\n",
      "(eds),\n",
      "\n",
      "sub-cellular\n",
      "In Alt-\n",
      "of\n",
      "Singapore,\n",
      "\n",
      "Proceedings\n",
      "\n",
      "Tsuruoka,Y. and Tsujii,J.\n",
      "\n",
      "(2004)\n",
      "\n",
      "in protein name recognition. J. Biomed.\n",
      "\n",
      "Improving the performance of dictionary-\n",
      "37,\n",
      "\n",
      "Inform.,\n",
      "\n",
      "Wagner,R. and Fischer,M. (1974) The string-to-string correction problem. J. ACM, 21,\n",
      "\n",
      "Watson,I. and Marir,F. (1994) Case-based reasoning: a review. Knowledge Eng. Rev., 9,\n",
      "\n",
      "based approaches\n",
      "461–470.\n",
      "\n",
      "168–173.\n",
      "\n",
      "327–354.\n",
      "\n",
      "l\n",
      "\n",
      "D\n",
      "o\n",
      "w\n",
      "n\n",
      "o\n",
      "a\n",
      "d\n",
      "e\n",
      "d\n",
      "\n",
      " \n",
      "f\n",
      "r\n",
      "o\n",
      "m\n",
      "h\n",
      "\n",
      " \n",
      "\n",
      "t\n",
      "t\n",
      "\n",
      "p\n",
      "s\n",
      ":\n",
      "/\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "a\n",
      "c\n",
      "a\n",
      "d\n",
      "e\n",
      "m\n",
      "c\n",
      ".\n",
      "o\n",
      "u\n",
      "p\n",
      ".\n",
      "c\n",
      "o\n",
      "m\n",
      "b\n",
      "o\n",
      "n\n",
      "o\n",
      "r\n",
      "m\n",
      "a\n",
      "\n",
      "f\n",
      "\n",
      "/\n",
      "\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "\n",
      "t\n",
      "i\n",
      "c\n",
      "s\n",
      "/\n",
      "a\n",
      "r\n",
      "t\n",
      "i\n",
      "c\n",
      "e\n",
      "-\n",
      "a\n",
      "b\n",
      "s\n",
      "t\n",
      "r\n",
      "a\n",
      "c\n",
      "t\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "/\n",
      "\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "7\n",
      "4\n",
      "8\n",
      "2\n",
      "9\n",
      "4\n",
      "6\n",
      "8\n",
      "1\n",
      "b\n",
      "y\n",
      " \n",
      "U\n",
      "n\n",
      "v\n",
      "e\n",
      "r\n",
      "s\n",
      "i\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "i\n",
      "\n",
      "ä\n",
      "t\n",
      "s\n",
      "b\n",
      "b\n",
      "\n",
      "i\n",
      "\n",
      "l\n",
      "i\n",
      "\n",
      "i\n",
      "\n",
      "t\n",
      "\n",
      " \n",
      "\n",
      "o\n",
      "h\n",
      "e\n",
      "k\n",
      " \n",
      "M\n",
      "a\n",
      "n\n",
      "n\n",
      "h\n",
      "e\n",
      "m\n",
      "u\n",
      "s\n",
      "e\n",
      "r\n",
      " \n",
      "o\n",
      "n\n",
      "0\n",
      "9\n",
      "M\n",
      "a\n",
      "y\n",
      " \n",
      "2\n",
      "0\n",
      "2\n",
      "0\n",
      "\n",
      " \n",
      "\n",
      " \n",
      "\n",
      "2758\n",
      "\n",
      "\f",
      "\n"
     ]
    }
   ],
   "source": [
    "\n",
    "from pdfminer.pdfinterp import PDFResourceManager, PDFPageInterpreter\n",
    "from pdfminer.converter import TextConverter\n",
    "from pdfminer.layout import LAParams\n",
    "from pdfminer.pdfpage import PDFPage\n",
    "from io import StringIO\n",
    "\n",
    "class PdfConverter:\n",
    "\n",
    "   def __init__(self, file_path):\n",
    "       self.file_path = file_path\n",
    "# convert pdf file to a string which has space among words \n",
    "   def convert_pdf_to_txt(self):\n",
    "       rsrcmgr = PDFResourceManager()\n",
    "       retstr = StringIO()\n",
    "       codec = 'utf-8'  # 'utf16','utf-8'\n",
    "       laparams = LAParams()\n",
    "       device = TextConverter(rsrcmgr, retstr, codec=codec, laparams=laparams)\n",
    "       fp = open(self.file_path, 'rb')\n",
    "       interpreter = PDFPageInterpreter(rsrcmgr, device)\n",
    "       password = \"\"\n",
    "       maxpages = 0\n",
    "       caching = True\n",
    "       pagenos = set()\n",
    "       for page in PDFPage.get_pages(fp, pagenos, maxpages=maxpages, password=password, caching=caching, check_extractable=True):\n",
    "           interpreter.process_page(page)\n",
    "       fp.close()\n",
    "       device.close()\n",
    "       str = retstr.getvalue()\n",
    "       retstr.close()\n",
    "       return str\n",
    "# convert pdf file text to string and save as a text_pdf.txt file\n",
    "   def save_convert_pdf_to_txt(self):\n",
    "       content = self.convert_pdf_to_txt()\n",
    "       txt_pdf = open('text_pdf.txt', 'wb')\n",
    "       txt_pdf.write(content.encode('utf-8'))\n",
    "       txt_pdf.close()\n",
    "if __name__ == '__main__':\n",
    "    pdfConverter = PdfConverter(file_path='bti338.pdf')\n",
    "    print(pdfConverter.convert_pdf_to_txt())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "768\n",
      "\n",
      "IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 35, NO. 4, AUGUST 2005\n",
      "\n",
      "A Fuzzy Reinforcement Learning Approach to Power\n",
      "Control in Wireless Transmitters\n",
      "\n",
      "David Vengerov, Nicholas Bambos, and Hamid R. Berenji, Fellow, IEEE\n",
      "\n",
      "Abstract—We address the issue of power-controlled shared\n",
      "channel access in wireless networks supporting packetized data\n",
      "trafﬁc. We formulate this problem using the dynamic program-\n",
      "ming framework and present a new distributed fuzzy reinforce-\n",
      "ment learning algorithm (ACFRL-2) capable of adequately solving\n",
      "a class of problems to which the power control problem belongs.\n",
      "Our experimental results show that the algorithm converges\n",
      "almost deterministically to a neighborhood of optimal parameter\n",
      "values, as opposed to a very noisy stochastic convergence of earlier\n",
      "algorithms. The main tradeoff facing a transmitter is to balance\n",
      "its current power level with future backlog in the presence of\n",
      "stochastically changing interference. Simulation experiments\n",
      "demonstrate that the ACFRL-2 algorithm achieves signiﬁcant\n",
      "performance gains over the standard power control approach used\n",
      "in CDMA2000. Such a large improvement is explained by the fact\n",
      "that ACFRL-2 allows transmitters to learn implicit coordination\n",
      "policies, which back off under stressful channel conditions as\n",
      "opposed to engaging in escalating “power wars.”\n",
      "\n",
      "Index Terms—Actor-critic algorithms,\n",
      "\n",
      "fuzzy reinforcement\n",
      "\n",
      "learning, wireless power control.\n",
      "\n",
      "I. INTRODUCTION\n",
      "\n",
      "U NLIKE the more traditional time-division multiple access\n",
      "\n",
      "(TDMA) or frequency-division multiple access (FDMA)\n",
      "wireless networks, the new generation of code-division multiple\n",
      "access (CDMA) networks do not restrict a priori the number of\n",
      "users that can share the same wireless channel. As new users\n",
      "are added to the channel, the quality of service of existing users\n",
      "gradually deteriorates due to increased mutual interference.\n",
      "\n",
      "Transmitter power control algorithms allow users to dynami-\n",
      "cally share the bandwidth of a wireless channel, optimizing the\n",
      "channel throughput. In addition, intelligent power control al-\n",
      "lows mobile users to extend their battery life.\n",
      "\n",
      "Since the previous generation of mobile phones did not have\n",
      "any data transfer capabilities, most of the algorithms consid-\n",
      "ered by the research literature [6]–[10] have focused just on\n",
      "optimizing the signal-to-interference (SIR) ratio, a character-\n",
      "istic requirement for voice-oriented “continuous” trafﬁc. For ex-\n",
      "ample, Foschini and Miljanic [6] introduced a simple distributed\n",
      "power control algorithm for maintaining a ﬁxed level of SIR,\n",
      "which was later adapted into the IS-95 standard and then into\n",
      "\n",
      "Manuscript received February 3, 2004; revised August 17, 2004. This paper\n",
      "\n",
      "was recommended by Editor J. B. Oommen.\n",
      "\n",
      "D. Vengerov is with Sun Microsystems Laboratories, Sunnyvale, CA 94086\n",
      "\n",
      "(e-mail: dive1743@yahoo.com).\n",
      "\n",
      "bambos@stanford.edu).\n",
      "\n",
      "N. Bambos is with Stanford University, Stanford, CA 94305 USA (e-mail:\n",
      "\n",
      "H. R. Berenji is with Intelligent Inference Systems Corporation, Mountain\n",
      "\n",
      "View, CA 94035 USA (e-mail: berenji@iiscorp.com).\n",
      "\n",
      "Digital Object Identiﬁer 10.1109/TSMCB.2005.846001\n",
      "\n",
      "CDMA2000. As a result, their algorithm also became a stan-\n",
      "dard benchmark in the research literature, against which all new\n",
      "algorithms are compared.\n",
      "\n",
      "Data trafﬁc is less sensitive to delays than voice trafﬁc, but\n",
      "it is more sensitive to transmission errors. Reliability can be\n",
      "assured via retransmissions, which cannot be used in continuous\n",
      "voice trafﬁc domains. Therefore, delay tolerance of data trafﬁc\n",
      "can be exploited for design of efﬁcient transmission algorithms\n",
      "that adapt the power level to the backlog of packets awaiting\n",
      "transmission as well as to the current interference level in the\n",
      "channel.\n",
      "\n",
      "The main dilemma that a data transmitter faces in controlling\n",
      "its power is the following. When high interference is observed\n",
      "in the channel, the transmitter recognizes that it will have to\n",
      "spend a lot of power to ensure successful transmission. There-\n",
      "fore, the transmitter might choose to back off, buffer the arriving\n",
      "packets and wait for the interference to subside before trans-\n",
      "mitting again. However, as the buffer is ﬁlling up with newly\n",
      "arriving packets, the queueing delay rises and the chance of\n",
      "buffer overﬂow increases, which pushes the transmitter to be-\n",
      "come more power-aggressive in order to reduce its backlog.\n",
      "\n",
      "When several transmitters are sharing the same channel, in-\n",
      "terference becomes responsive to transmitter’s actions. That is,\n",
      "a power-aggressive transmitter may cause other ones to go into\n",
      "a backoff mode or also become aggressive. Therefore, optimal\n",
      "transmission policies should consider not only the channel dy-\n",
      "namics but also patterns in the behavior of other transmitters.\n",
      "Since this information is not known a priori, it needs to be\n",
      "learned through direct interaction with the channel or with a\n",
      "simulation model.\n",
      "\n",
      "The reinforcement learning [11] framework can be used for\n",
      "learning optimal behavior policies in situations such as the one\n",
      "described above. To the best of our knowledge, no reinforcement\n",
      "learning algorithms have been applied to the data power control\n",
      "problem, and the only analytical investigations of this problem\n",
      "formulation are due to Bambos and Kandukuri [2]. They have\n",
      "derived an optimal policy for a single wireless transmitter when\n",
      "interference is random and either follows a uniform distribu-\n",
      "tion or has a Markovian structure. In reality, distribution of in-\n",
      "terference is not known a priori, and the analytical solution of\n",
      "Bambos and Kandukuri cannot be applied.\n",
      "\n",
      "The paper is organized as follows. In Section II we present a\n",
      "centralized dynamic programming formulation of the problem\n",
      "faced by multiple transmitters sharing the same channel. We\n",
      "then show that the DP approach cannot provide even a numer-\n",
      "ical solution to this problem for realistic sizes of the state space\n",
      "due to the curse of dimensionality. In Section III we present\n",
      "a distributed reinforcement learning algorithm, ACFRL, that\n",
      "\n",
      "1083-4419/$20.00 © 2005 IEEE\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "\f",
      "769\n",
      "\n",
      "(3)\n",
      "\n",
      "(4)\n",
      "\n",
      "(5)\n",
      "\n",
      "VENGEROV et al.: FUZZY REINFORCEMENT LEARNING APPROACH\n",
      "\n",
      "has a much lower computational complexity and is theoreti-\n",
      "cally capable of solving this problem. In Section IV we describe\n",
      "ACFRL-2—an adaptation of ACFRL, which has a much faster\n",
      "initial convergence and can thus be deployed in real applica-\n",
      "tions. The ACFRL-2 algorithm is designed to work off-line with\n",
      "a system simulator, and after a good enough policy has been\n",
      "learned, it can be deployed in real time and ﬁne-tuned online\n",
      "using ACFRL. The convergence properties of the ACFRL-2 al-\n",
      "gorithm are analyzed in Section V. In Section VI we describe the\n",
      "simulation setup for our experiments of applying ACFRL-2 to\n",
      "the problem of transmitter power control in wireless networks.\n",
      "In Section VII we present simulation results for the ACFRL-2\n",
      "algorithm and discuss the implications of these results. Sec-\n",
      "tion VIII concludes the paper.\n",
      "\n",
      "II. DYNAMIC PROGRAMMING FORMULATION\n",
      "\n",
      "Our formulation of the wireless power control problem fol-\n",
      "lows that of Bambos and Kandukuri [2]. We consider a com-\n",
      "munication link operating in discrete time, indexed by\n",
      "\n",
      ". Let\n",
      "\n",
      ". The transmitter is equipped with a FIFO queue\n",
      "be the power that the th transmitter\n",
      "(buffer) of size\n",
      "uses to transmit a packet during the\n",
      "be\n",
      "the power gain (loss) from the transmitter of the th link to the\n",
      "receiver of the th one. The interference experienced by th link\n",
      "at any point of time is given by\n",
      "\n",
      "th time slot. Let\n",
      "\n",
      "the backlog cost\n",
      "linear cost function\n",
      "\n",
      ". For simplicity, we consider the case of a\n",
      "\n",
      "The objective of transmitter\n",
      "\n",
      "erage cost over all\n",
      "\n",
      "is to minimize the av-\n",
      "time steps by controlling the powers\n",
      "in consecutive time slots.\n",
      "\n",
      "The problem described above naturally falls within the realm\n",
      "of dynamic programming. We will now analyze the complexity\n",
      "of the dynamic programming solution to the above problem,\n",
      "simpliﬁed by assuming only two transmitters, no packet arrivals,\n",
      "deterministic ,\n",
      "be the\n",
      "optimal cost to go at time , deﬁned according to the Bellman’s\n",
      "principle of optimality using equation below, where backlog,\n",
      "interference, and power are all referring to the th time step and\n",
      "are indexed according to the transmitter-receiver link\n",
      "\n",
      ", and cost weight\n",
      "\n",
      ". Let\n",
      "\n",
      "(1)\n",
      "\n",
      "(2)\n",
      "\n",
      "where\n",
      "\n",
      "If the channel interference is\n",
      "\n",
      "is the thermal noise power at its receiver node [1].\n",
      "is used to transmit\n",
      "and power\n",
      "a packet in a time slot, then the packet is successfully received\n",
      "with probability\n",
      "\n",
      "where (1) was used to determine the connection between\n",
      "the power used by one transmitter and the interference ob-\n",
      "is a short hand for\n",
      "served at the other receiver and\n",
      ". The boundary constraint for this problem is\n",
      "\n",
      "where\n",
      "mission noise.\n",
      "\n",
      ", with higher values indicating higher level of trans-\n",
      "\n",
      "is the terminal cost due to backlog remaining in\n",
      "\n",
      "where\n",
      "the queue of the th transmitter.\n",
      "\n",
      "We assume for simplicity that conditional on (p,I), packet\n",
      "transmission events of any transmitter are statistically indepen-\n",
      "dent of each other. If transmission succeeds, the packet is re-\n",
      "moved from the queue and the transmitter attempts to transmit\n",
      "the next packet in the queue. If transmission does not succeed,\n",
      "the packet remains at the head of the queue for later retransmis-\n",
      "sion. We assume that the transmitter is immediately notiﬁed at\n",
      "the end of each time slot whether or not the packet was received\n",
      "successfully. The notiﬁcation message also contains the value of\n",
      "the interference observed at the receiver, which stays constant\n",
      "until the beginning of the next time step.\n",
      "\n",
      "Finally, we denote by\n",
      "\n",
      "the backlog of transmitter\n",
      "\n",
      "(number of packets in the transmitter’s queue) at time . When\n",
      "is\n",
      "a packet arrives to a full buffer, it gets dropped and a cost\n",
      "incurred.\n",
      "\n",
      "The task of transmitter\n",
      "each time step the power\n",
      "observing the current interference level\n",
      "backlog\n",
      "which is based on two components: the power cost\n",
      "\n",
      "is to choose at the beginning of\n",
      "to transmit the head packet after\n",
      "and the current\n",
      "th link incurs a cost\n",
      "and\n",
      "\n",
      ". In each time slot\n",
      "\n",
      "the\n",
      "\n",
      "In order to evaluate\n",
      "\n",
      "analytically, derivatives of the right-\n",
      "need to be\n",
      "and\n",
      "hand side (r.h.s) of (4) with respect to\n",
      "computed and set simultaneously to 0. However, solution of\n",
      "the two simultaneous equation will involve logarithms of dif-\n",
      "ferences of functions, which can only be solved numerically.\n",
      "Thus, we might as well carry out the numerical minimization of\n",
      "the r.h.s. of (4) right away, by numerically computing the deriva-\n",
      "and using a ﬁrst or second order gradient method.\n",
      "tives of\n",
      "In the simplest case of a ﬁrst order method, each optimization\n",
      "in order to compute the\n",
      "step would require 8 evaluations of\n",
      "computa-\n",
      "required derivatives. If evaluation of\n",
      "we would need to make\n",
      "tions, then in order to evaluate\n",
      "computations. Therefore, solving (4) through numer-\n",
      "ical optimization is possible only for very short time horizons.\n",
      "Another alternative for solving (4) is to discretize each state\n",
      "at each of those points.\n",
      "computations, then evaluation of\n",
      "computations. While this is feasible\n",
      "transmitters\n",
      "for the case of\n",
      "computations. This is not possible with the\n",
      "\n",
      "variable into\n",
      "If each evaluation takes\n",
      "will require\n",
      "for 2 transmitters, solving\n",
      "will require\n",
      "\n",
      "points and evaluate\n",
      "\n",
      "requires\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "\f",
      "770\n",
      "\n",
      "IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 35, NO. 4, AUGUST 2005\n",
      "\n",
      "current computer power for the realistic case of\n",
      "\n",
      "and\n",
      ". Thus, we can conclude, that even the simpliﬁed version\n",
      "of the multitransmitter power control problem cannot be solved\n",
      "using dynamic programming methods for realistic scenarios.\n",
      "\n",
      "III. REINFORCEMENT LEARNING SOLUTION\n",
      "\n",
      "Approximate dynamic programming approach [5] relies on\n",
      "using function approximation architectures for dealing with the\n",
      "curse of dimensionality and on domain simulations for esti-\n",
      "mating the problem uncertainties and tuning the parameters of\n",
      "these architectures. This approach is also sometimes called rein-\n",
      "forcement learning, since it uses online learning in the following\n",
      "Markov decision process framework: a learner observes its state,\n",
      "selects and implements the most appropriate action for this state,\n",
      "transfers to a new state, observes reinforcement (cost or reward)\n",
      "associated with this transition, observes the new state, etc.\n",
      "\n",
      "Recently, Konda and Tsitsiklis [12] presented an approxi-\n",
      "mate DP algorithm based on the actor-critic (AC) paradigm [13]\n",
      "and proved convergence of actor’s parameters to a local op-\n",
      "timum under certain technical assumptions. After that, Berenji\n",
      "and Vengerov [3], [4] instantiated their algorithm with a fuzzy\n",
      "rulebase actor and proved that it satisﬁes the convergence as-\n",
      "sumptions of Konda and Tsitsiklis. However, their Actor-Critic\n",
      "Based Fuzzy Reinforcement Learning (ACFRL) algorithm con-\n",
      "verged extremely slowly in the power control problem, where\n",
      "the memory of each learner’s action is long-lasting and at the\n",
      "same time a lot of randomness is present in the problem. In fact,\n",
      "in many experiments, the ACFRL algorithm did not show any\n",
      "signs of convergence during any reasonable length of time (up to\n",
      "an hour of simulation time—millions of simulated time steps).\n",
      "In the next section we describe our new algorithm (ACFRL-2)\n",
      "extending the prior work in [12] and [3] and [4], which avoids\n",
      "the problem of slow convergence and can thus be deployed in\n",
      "real applications. Before explaining the modiﬁcations done in\n",
      "ACFRL-2, we ﬁrst present the general actor-critic framework\n",
      "proposed by Konda and Tsitsiklis (K&T).\n",
      "\n",
      "The actor in their framework represents a mapping be-\n",
      "tween states and actions for the learner (e.g. mapping between\n",
      "backlog/interference observations and the transmitter’s power),\n",
      "and the critic represents an adviser to the actor, which evaluates\n",
      "actor’s performance. The actor then uses this performance\n",
      "evaluation to change its parameters in the gradient direction,\n",
      "minimizing the average cost per time step.\n",
      "\n",
      "domized stationary policy\n",
      "\n",
      ", which assigns to each state\n",
      "\n",
      "More formally, an actor in the K&T framework is a ran-\n",
      "parameterized by a vector\n",
      "of\n",
      "choosing action\n",
      "are assumed\n",
      ". Both of the sets\n",
      "to be discrete. The critic performs its evaluation by learning the\n",
      ", mapping state–action pairs into\n",
      "Q-function\n",
      "“Q-values.” In order to deﬁne the Q-function, we ﬁrst need to\n",
      "parameterized by a\n",
      "deﬁne the average cost\n",
      "vector\n",
      "\n",
      "a probability\n",
      "and\n",
      "\n",
      "for an\n",
      "\n",
      "where\n",
      "is a steady state probability of being in state\n",
      "\n",
      "is the cost of selecting action in state and\n",
      "\n",
      "under\n",
      "\n",
      "(6)\n",
      "\n",
      ".\n",
      "\n",
      "Then, the “differential cost function”\n",
      "a solution to the Poisson equation\n",
      "\n",
      "is deﬁned as\n",
      "\n",
      "is the probability of transferring to a state\n",
      "\n",
      "where\n",
      "from state\n",
      "can be\n",
      "interpreted as the expected future excess cost, with respect to\n",
      ", if the actor is started in state . Finally,\n",
      "the average cost\n",
      "\n",
      "is selected. Intuitively,\n",
      "\n",
      "if action\n",
      "\n",
      "is deﬁned by\n",
      "\n",
      "If the Q-values associated with the optimal policy are available\n",
      "for all state–action pairs, then the optimal policy can be enacted\n",
      ". This\n",
      "by taking in each state the action that maximizes\n",
      "observation is central to the widely used Q-learning approach\n",
      "to solving reinforcement learning problems. While the iterative\n",
      "Q-learning approach converges to the optimal Q-values, in prac-\n",
      "tice it can be carried out only for small state and action spaces,\n",
      "where every action can be performed in every state inﬁnitely\n",
      "many times. As the size of the state space grows, visiting every\n",
      "state becomes more and more improbable, and Q-values need\n",
      "to be generalized across similar states using a function approxi-\n",
      "mation architecture. More importantly, as the size of the action\n",
      "space grows, it becomes more and more difﬁcult to sample every\n",
      "action in any given state. Therefore, presence of a parameterized\n",
      "actor (function approximation architecture), which maps states\n",
      "into actions, is required in problems with very large state and\n",
      "action spaces.\n",
      "\n",
      "The K&T framework relies on the following inner product\n",
      "\n",
      "expression of the average cost gradient\n",
      "\n",
      "where\n",
      "and\n",
      "the probability of encountering the state–action pair\n",
      "\n",
      "is the th basis function\n",
      "is the weighting factor, giving\n",
      "under\n",
      ". Analysis of the above equation shows that in order for\n",
      "the actor to change its parameters along the gradient of average\n",
      "cost, it needs to receive from the critic only a projection of the\n",
      ",\n",
      "optimal Q-function onto the space of the basis functions\n",
      "since the inner product of any two vectors\n",
      "and is the product\n",
      "onto . That is,\n",
      "and\n",
      "of magnitudes of\n",
      "if\n",
      "\n",
      "is this projection, then\n",
      "\n",
      ", the projection of\n",
      "\n",
      "Since\n",
      "\n",
      "is a projection onto the space of the basis functions\n",
      "\n",
      ", it can be expressed as\n",
      "\n",
      "(7)\n",
      "\n",
      "(8)\n",
      "\n",
      "(9)\n",
      "\n",
      "(10)\n",
      "\n",
      "(11)\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "\f",
      "VENGEROV et al.: FUZZY REINFORCEMENT LEARNING APPROACH\n",
      "\n",
      "771\n",
      "\n",
      "for some vector\n",
      "framework learns the parameter vector\n",
      "\n",
      ". The critic in the K&T\n",
      ", which approximates\n",
      ", an estimate of the average cost per\n",
      "\n",
      ". The critic also stores\n",
      "\n",
      "step under the current policy, which is updated according to\n",
      "\n",
      "The critic’s parameter vector\n",
      "\n",
      "is updated as follows:\n",
      "\n",
      "is the critic’s learning rate at time ,\n",
      "\n",
      "where\n",
      "imation to\n",
      "eligibility trace, to be described shortly. For any\n",
      "and 1, the\n",
      "critic updates\n",
      "\n",
      "according to\n",
      "\n",
      "in terms of\n",
      "\n",
      "and\n",
      "\n",
      "(13)\n",
      "is an approx-\n",
      "is an -vector, called the\n",
      "between 0\n",
      "\n",
      "The actor updates its parameters according to\n",
      "\n",
      "where\n",
      "\n",
      "is the actor’s learning rate at time .\n",
      "\n",
      "into a scalar output\n",
      "\n",
      "that maps an input vector\n",
      "\n",
      "In order to apply the above framework to any problem, the\n",
      "needs to be selected. Following the\n",
      "functional form of\n",
      "work of Berenji and Vengerov [3], [4], we have used a fuzzy\n",
      "for the power control problem. A\n",
      "rulebase as the core of\n",
      "fuzzy rulebase needed for our purposes is a function that maps\n",
      ". This function is\n",
      "an input vector\n",
      "is a\n",
      "represented by a collection of fuzzy rules. A fuzzy rule\n",
      "function\n",
      ".\n",
      "We have used the following fuzzy rules.\n",
      ") and\n",
      ",\n",
      "\n",
      "(\n",
      ") THEN\n",
      "is the th component of\n",
      "are input labels in\n",
      "are tunable coefﬁcients. Each label is a function\n",
      "that maps its input into a degree to which this input\n",
      "belongs to the fuzzy category (linguistic term) described by the\n",
      "label. The exact shape of the input labels for the power control\n",
      "problem will be given in Section VI. A fuzzy rulebase actor\n",
      "with\n",
      "\n",
      "Rule : IF (\n",
      ", where\n",
      "and\n",
      "\n",
      "rules can then be expressed as\n",
      "\n",
      "into a scalar\n",
      "\n",
      ") and (\n",
      "\n",
      "rule\n",
      "\n",
      "is\n",
      "\n",
      "is\n",
      "\n",
      "is\n",
      "\n",
      "where\n",
      "inference for computing the weight of each rule:\n",
      "\n",
      "is the weight of rule . We used the product\n",
      "\n",
      ". Finally, the power used by the transmitter is\n",
      "\n",
      "sampled from a Gaussian distribution centered at\n",
      "\n",
      "The Gaussian distribution was chosen only for the ease of com-\n",
      "puter simulation. As Section V will show, any symmetric prob-\n",
      "ability mass function could have been used, which assigns a\n",
      "nonzero probability to selecting every possible action. Also,\n",
      "while the proof is carried out only for discrete action spaces,\n",
      "the ACFRL-2 algorithm can work just as well for continuous ac-\n",
      "tions spaces, and Section VI provides experimental results con-\n",
      "ﬁrming this claim.\n",
      "\n",
      "(12)\n",
      "\n",
      "(14)\n",
      "\n",
      "(15)\n",
      "\n",
      "(16)\n",
      "\n",
      "(17)\n",
      "\n",
      "As will be explained in Section VI, the parameters will rep-\n",
      "resent the recommended power output for each fuzzy state ob-\n",
      "served by the transmitter. These parameters will form the vector\n",
      "tuned by the ACFRL-2 algorithm. In the next section we de-\n",
      "scribe the ACFRL-2 algorithm (which we apply to both single\n",
      "and multiple transmitter problems) and in Section V we analyze\n",
      "its convergence properties for the case of the single transmitter\n",
      "problem.\n",
      "\n",
      "IV. ACFRL-2 ALGORITHM\n",
      "\n",
      "The main difﬁculty in the considered power control problem\n",
      "is that a long wait is required for learning the beneﬁt of using\n",
      "a higher or a lower transmission power in each state. That is,\n",
      "a smaller than average cost per step can be incurred because\n",
      "successfully\n",
      "a higher than recommended power used at time\n",
      "transmitted a packet and decreased the future backlog for\n",
      ".\n",
      "be-\n",
      "However, the backlog can stay at low levels for\n",
      "cause fewer packets have arrived into the transmitter, which\n",
      "will affect all the future costs until the systems renews itself\n",
      "by emptying the backlog. The difﬁculty of determining the ef-\n",
      "fects of using a higher or a lower power is aggravated by the\n",
      "fact that the near-optimal policies use decreasing transmission\n",
      "power for lower values of backlog, which makes renewals very\n",
      "infrequent. As a result, it takes a very long time to learn accu-\n",
      "rate Q-values for randomized stationary policies (RSPs) in prob-\n",
      "lems with characteristics described above. Therefore, the K&T\n",
      "framework, which continually adapts the Q-values and simul-\n",
      "taneously uses them to update an RSP-type actor will lead to\n",
      "a very long and noise learning, as was conﬁrmed by our initial\n",
      "experiments in the power control problem.\n",
      "\n",
      "We propose a solution to this problem, which consists of de-\n",
      "in each state\n",
      "using\n",
      "and then learning the\n",
      "\n",
      "termining the most likely action\n",
      "the current fuzzy rulebase parameters\n",
      "Q-values for two separate policies, one sampling actions\n",
      "\n",
      "and the other sampling actions\n",
      "\n",
      "in all en-\n",
      "countered states. As a result, the critic can clearly observe the\n",
      "long-term effects of using a higher or a lower power in all states,\n",
      "which makes it much easier to deduce the correct direction for\n",
      "changing actor’s parameters.\n",
      "\n",
      "Implementing this idea is particularly simple with\n",
      "\n",
      "being a fuzzy rulebase giving the mean of the Gaussian distribu-\n",
      "tion from which the ﬁnal output is sampled. More speciﬁcally,\n",
      "implementing ACFRL-2 requires separating the updates to the\n",
      "average cost per step, critic’s parameters and actor’s parameters\n",
      "into distinct phases. During the ﬁrst phase, the algorithm sim-\n",
      "time steps to estimate the average cost\n",
      "ulates the system for\n",
      "per step of the actor’s policy. In the second phase only critic is\n",
      "obtained during the pre-\n",
      "learning based on the average cost\n",
      "vious phase. This phase consists of two simulation traces, one\n",
      "sampling actions from the positive half of a Gaussian distribu-\n",
      "tion centered at the value recommended by the current form of\n",
      "the fuzzy rulebase actor and one sampling actions from the neg-\n",
      "ative half of this Gaussian distribution. Correspondingly, two\n",
      "parameter vectors\n",
      "\n",
      "are learned.\n",
      "\n",
      "and\n",
      "\n",
      "Finally, in the third phase, the critic is ﬁxed and the actor is\n",
      "learning using (15). The actions for the actor are sampled from\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "\f",
      "772\n",
      "\n",
      "IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 35, NO. 4, AUGUST 2005\n",
      "\n",
      "the full Gaussian distribution. However, when the sampled ac-\n",
      "tion is higher than the average power suggested by its fuzzy\n",
      "is used to compute the\n",
      "rulebase, the critic’s parameter vector\n",
      "Q-value of the current state–action pair in (15). Similarly, when\n",
      "the sampled action is lower than the average power suggested by\n",
      "is used for\n",
      "the fuzzy rulebase, the critic’s parameter vector\n",
      "computing the Q-value. The above three phased are repeated for\n",
      "a desired number of time steps until the learned policy performs\n",
      "well enough for practical purposes. If the maximum possible\n",
      "accuracy is desired and the time is not an issue, the above three\n",
      "phases are repeated until any of the actor’s parameters begins to\n",
      "oscillate around some value, which indicates that the neighbor-\n",
      "hood of the optimal values has been reached. At that point, one\n",
      "can switch to the ACFRL algorithm to perform the ﬁne-tuning\n",
      "of actor’s parameters.\n",
      "\n",
      "As opposed to the fully probabilistic exploration at every time\n",
      "step suggested by Konda and Tsitsiklis, the systematic explo-\n",
      "ration described above is very beneﬁcial in highly stochastic\n",
      "problems with long renewal periods and long-lasting memory of\n",
      "actions, as it allows the critic to observe more clearly the beneﬁt\n",
      "of each action. Our experimental results show that the ACFRL-2\n",
      "algorithm converges to the neighborhood of optimal parame-\n",
      "ters almost deterministically (moving every actor’s parameter\n",
      "in the right direction after every repetition of the three-phase\n",
      "procedure described above), while the ACFRL algorithm moves\n",
      "actor’s parameters almost as an unbiased random walk even\n",
      "when all parameters are obviously lower or higher than their\n",
      "optimal values.\n",
      "\n",
      "V. CONVERGENCE PROPERTIES OF ACFRL-2\n",
      "\n",
      "In this section we analyze the convergence properties of the\n",
      "ACFRL-2 algorithm for the case of a single transmitter facing\n",
      "environment with interference sampled from any ﬁxed proba-\n",
      "bility mass function (PMF). We assume that\n",
      "is a sym-\n",
      "metric PMF, which assigns a nonzero probability to selecting\n",
      "every possible action. We ﬁrst present sufﬁcient convergence\n",
      "assumptions for the general K&T framework for the case of ﬁ-\n",
      "nite state and action spaces.\n",
      "\n",
      "A0) The learning rate sequences\n",
      "\n",
      ",\n",
      "\n",
      "are positive,\n",
      "\n",
      "nonincreasing, and satisfy\n",
      "\n",
      "as well as\n",
      "\n",
      "where\n",
      "\n",
      "stands for either\n",
      "\n",
      "or\n",
      "\n",
      ".\n",
      "\n",
      ", the Markov chains\n",
      "\n",
      "A1) For each\n",
      "and\n",
      "and aperiodic, with stationary distributions\n",
      "\n",
      "of states\n",
      "of state–action pairs are irreducible\n",
      "and\n",
      ", respectively, under the RSP\n",
      "\n",
      ".\n",
      "\n",
      "A2) For all\n",
      "\n",
      "and\n",
      "\n",
      ", the map\n",
      "\n",
      "is twice\n",
      "\n",
      "differentiable.\n",
      "\n",
      "A3)\n",
      "A4) The feature vectors\n",
      "\n",
      ", and for all\n",
      "\n",
      ",\n",
      "\n",
      ",\n",
      "\n",
      ".\n",
      "\n",
      "uniformly linearly independent. That is, there exists\n",
      "\n",
      "such that for all\n",
      "\n",
      ",\n",
      "\n",
      "are\n",
      "\n",
      "(18)\n",
      "\n",
      "The sum conditions in assumptions A0 are the standard re-\n",
      "quirements for a stochastic gradient algorithm to converge. The\n",
      "condition on the ratio of the learning rates ensure that asymptot-\n",
      "ically the actor seems stationary to the critic, which allows the\n",
      "critic to learn asymptotically the accurate gradient direction for\n",
      "changing actor’s parameters.\n",
      "\n",
      "Assumption A1 is required to ensure that the average cost in\n",
      "the considered problem is well deﬁned. The stochastic nature of\n",
      "arrival and departures from the ﬁnite buffer model of the wire-\n",
      "less transmitter ensures that the backlog forms an irreducible\n",
      "and aperiodic Markov chain. Since interference is assumed to\n",
      "be randomly sampled from a ﬁxed PMF, the total state com-\n",
      "bining backlog and interference satisﬁes assumption A1. Since\n",
      "actions are chosen from a ﬁxed PMF, the sequence of state–ac-\n",
      "also forms an irreducible and aperiodic\n",
      "tion pairs\n",
      "Markov chain. Assumptions A2 and A3 are sufﬁcient assump-\n",
      "to be well\n",
      "tions in order for the gradient of the average cost\n",
      "deﬁned and expressed compactly as in (9).\n",
      "\n",
      "Assumption A2 can be veriﬁed directly, by differentiating the\n",
      "output of the actor with respect to all parameters and observing\n",
      "that all derivatives exist. To save space, we point the reader to\n",
      "[4] for exact expressions of these derivatives. Assumption A3\n",
      "holds because of the action PMF properties we assumed at the\n",
      "beginning of this section.\n",
      "\n",
      "In order to understand the need for Assumption A4, note that\n",
      "when the actor’s parameter vector is , the critic attempts to ap-\n",
      "proximate the projection of the actual Q-value onto the space of\n",
      "actor’s features, as shown in (11). If the actor’s features are lin-\n",
      "early dependent, the projection operator is ill-conditioned. This\n",
      "possibility is prevented by assumption A4. This assumption was\n",
      "veriﬁed for the proposed fuzzy rulebase actor by Berenji and\n",
      "Vengerov [4].\n",
      "\n",
      "The above assumptions are sufﬁcient to guarantee conver-\n",
      "gence of the K&T framework if all actions are sampled in\n",
      "every state, which is done in ACFRL. However, separating\n",
      "exploration into two parts in ACFRL-2 creates unexpected\n",
      "difﬁculties, even though each action is chosen in the long\n",
      "run with the same frequency as when all actions are sampled\n",
      "of\n",
      "in ACFRL. That is, while in ACFRL the same vector\n",
      "critic’s parameters gets updated whether the ﬁnal action is\n",
      "sampled from the right side of the PMF or from the left side,\n",
      "in ACFRL-2 we cannot simply average the resulting vectors\n",
      "and\n",
      "for\n",
      "time steps while the actor is held ﬁxed. Intuitively, the reason\n",
      "for this is that different sampling policies have different basis\n",
      ", and hence parameter\n",
      "vectors\n",
      "vectors\n",
      "\n",
      "obtained after sampling from the right side of the PMF\n",
      "time steps and then sampling from the left side for\n",
      "\n",
      "in (11) cannot simply be averaged.\n",
      "\n",
      "; otherwise,\n",
      "\n",
      "More precisely, let\n",
      "\n",
      "be the transmission power suggested\n",
      "by the actor’s fuzzy rulebase in the state . If the ﬁnal action is\n",
      "sampled from the right side of the PMF centered at\n",
      ", then\n",
      ". Now, observe that for any\n",
      ",\n",
      ", where\n",
      "is a matrix with\n",
      "is a vector of Q-values for\n",
      "be the “top half” of\n",
      "\n",
      "ﬁxed , the ACFRL critic learns to approximate the vector\n",
      "giving the solution to\n",
      "columns\n",
      ",\n",
      "all state–action pairs in\n",
      "with entries\n",
      "\n",
      "that correspond to state–action pairs with\n",
      "with\n",
      "be the “bottom half” of\n",
      "\n",
      ". Similarly, let\n",
      "\n",
      ". Let\n",
      "\n",
      "and\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "\f",
      "VENGEROV et al.: FUZZY REINFORCEMENT LEARNING APPROACH\n",
      "\n",
      "entries that correspond to state–action pairs with\n",
      "Let the components of\n",
      "that\n",
      "and\n",
      "and\n",
      "\n",
      ".\n",
      "be ordered in such a way\n",
      "be the “top half” of\n",
      ". Let the components of\n",
      ".\n",
      "\n",
      "be the “bottom half” of\n",
      "be arranged so that\n",
      "\n",
      "and\n",
      ". Also, let\n",
      "\n",
      "and\n",
      "\n",
      "When sampling from the right side and from the left side of\n",
      "the action PMF, ACFRL-2 aims to learn differential Q-functions\n",
      "of the\n",
      "with respect to the same average cost\n",
      ", which samples all actions. That is, when the actor is\n",
      "policy\n",
      "ﬁxed and phase 2 of the ACFRL-2 is repeated continually, the\n",
      "critic converges to\n",
      "\n",
      "such that\n",
      "\n",
      "and\n",
      "\n",
      "probability of being in a state\n",
      "policy\n",
      "\n",
      ". Then, rewriting (10) in the matrix form\n",
      "\n",
      "and choosing action under the\n",
      "\n",
      "from the r.h.s. of the\n",
      "where we have omitted the subscript\n",
      "above equation and from the rest of the discussion to make no-\n",
      "tation less cumbersome.\n",
      "Let the components of\n",
      "\n",
      "be arranged so that the top half of\n",
      "the diagonal contains entries corresponding to state–action pairs\n",
      "and the bottom half of the diagonal contains en-\n",
      "with\n",
      ". Then,\n",
      "tries corresponding to state–action pairs with\n",
      "we want to show that\n",
      "\n",
      "(19)\n",
      "\n",
      "and\n",
      "\n",
      "where\n",
      "are the error terms. These errors are intro-\n",
      "duced because the restricted exploration during the critic’s\n",
      "learning in ACFRL-2 samples states according to a different\n",
      "steady-state distribution than the one resulting from the full\n",
      ", then we\n",
      "exploration. Therefore, if we average\n",
      "have\n",
      ",\n",
      ".\n",
      "\n",
      "and\n",
      "\n",
      ",\n",
      "\n",
      "Since we have no control over\n",
      "and\n",
      "of policy\n",
      "\n",
      "performing the full exploration.\n",
      "\n",
      "can lead to a very poor approximation of the Q-function\n",
      "\n",
      "and\n",
      "\n",
      ", averaging\n",
      "\n",
      "Therefore, as suggested in Section IV, the ACFRL-2 critic\n",
      "obtained during its learning\n",
      "simply stores the vectors\n",
      "phase and then computes the Q-value of a state–action pair (s,a)\n",
      "during actor’s update in phase III of the algorithm as\n",
      "\n",
      "and\n",
      "\n",
      "if was sampled from the right side of the\n",
      "if was sampled from\n",
      "\n",
      "PMF and as\n",
      "the left side of the PMF.\n",
      "\n",
      "Theorem 1: When the actor’s parameters are ﬁxed at\n",
      "\n",
      "and\n",
      "phase 2 of the ACFRL-2 is repeated continually, the critic con-\n",
      "verges to when sampling actions from the left side of the ac-\n",
      "when sampling actions from the right side.\n",
      "tion PMF and to\n",
      "Moreover, these vectors can be used to provide the gradient di-\n",
      "rection for changing the actor’s parameters using the above pro-\n",
      "cedure if all parameters lie on the same side of their optimal\n",
      "values (i.e.,\n",
      "is the optimal param-\n",
      "eter vector).\n",
      "\n",
      ", where\n",
      "\n",
      "or\n",
      "\n",
      "Proof: Convergence of the critic to\n",
      "if actions are sam-\n",
      "pled only from the left side of the PMF and to\n",
      "if actions are\n",
      "sampled only from the right side follows from the results es-\n",
      "learning converges with a linear ap-\n",
      "tablished in [14]:\n",
      "proximation architecture if the states are sampled according to\n",
      "the steady-state distribution resulting from applying the cur-\n",
      "rent policy, which is the case during on-policy exploration. A\n",
      "more technical condition required for convergence of\n",
      "is\n",
      "a linear independence of feature functions, whose linear combi-\n",
      "nation is used to approximate the optimal Q-value. This condi-\n",
      "tion holds in ACFRL-2 because of assumption A4.\n",
      "\n",
      "It now remains to prove that the optimal parameter vectors\n",
      "for the ACFRL-2 critic provide the gradient direction for the\n",
      "actor. Let\n",
      "for all\n",
      "be a diagonal matrix with entries\n",
      "state–action pairs (s,a), where each entry gives a steady state\n",
      "\n",
      ",\n",
      "In the proof below, we will consider only the case of\n",
      "since the same reasoning but with opposite signs will hold in the\n",
      "case when\n",
      "\n",
      ".\n",
      "\n",
      "With the policy\n",
      "\n",
      "given by (17), we have\n",
      "\n",
      "Therefore, as the above equation shows, the use of a sym-\n",
      "that\n",
      "metric PMF for exploration in ACFRL-2 implies\n",
      ". As\n",
      "\n",
      "for\n",
      "\n",
      "a result,\n",
      "\n",
      ", which implies that\n",
      "\n",
      "As was explained at the end of Section III,\n",
      "\n",
      "is the transmis-\n",
      "\n",
      "sion power suggested by the th fuzzy rule. Therefore,\n",
      "implies that in each state it is more preferable to use a higher\n",
      "transmission power than a lower one. That is, if\n",
      "then\n",
      ". Furthermore, since\n",
      "\n",
      "from (23), we have\n",
      "\n",
      "Recalling the arrangement of components of\n",
      "and using (22) we get that\n",
      "\n",
      "Combining this result with (24), we get\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "which is consistent with\n",
      "\n",
      ", as (20) shows that increasing\n",
      "\n",
      "will decrease\n",
      "\n",
      ".\n",
      "\n",
      "773\n",
      "\n",
      "(20)\n",
      "\n",
      "(21)\n",
      "\n",
      "(22)\n",
      "\n",
      "(23)\n",
      "\n",
      "(24)\n",
      "\n",
      "(25)\n",
      "\n",
      "(26)\n",
      "\n",
      "\f",
      "774\n",
      "\n",
      "IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 35, NO. 4, AUGUST 2005\n",
      "\n",
      "Let us consider now the signs of\n",
      "\n",
      "and\n",
      "\n",
      ". Recall that\n",
      "\n",
      "and\n",
      "\n",
      "are deﬁned by equations\n",
      "\n",
      "sults is not necessary to achieve good performance in the power\n",
      "control problem.\n",
      "\n",
      "(27)\n",
      "(28)\n",
      "\n",
      "(29)\n",
      "\n",
      "(30)\n",
      "\n",
      "where\n",
      "is a vector of Q-values for the policy that uses a\n",
      "higher than recommended power in each state by sampling it\n",
      "is a vector of\n",
      "from the right side of the PMF. Similarly,\n",
      "Q-values for the policy that uses a lower than recommended\n",
      "power in each state by sampling it from the left side of the PMF.\n",
      "Also, recall that by construction of the ACFRL-2 algorithm both\n",
      "are differential Q-value vectors with respect to\n",
      "the same average cost\n",
      "of the policy that samples all actions.\n",
      "and the fuzzy rulebase actor conse-\n",
      "Therefore, when\n",
      "quently recommends in all states a smaller than optimal trans-\n",
      "mission power, we have\n",
      "\n",
      "and\n",
      "\n",
      "in state\n",
      "\n",
      "because\n",
      "denotes expected average cost per step after\n",
      "and following a more beneﬁcial (the\n",
      "taking action\n",
      "one with a smaller expected average cost) policy thereafter than\n",
      "denotes\n",
      "is computed. Similarly,\n",
      "the one for which\n",
      "expected average cost per step after taking action\n",
      "and following a less beneﬁcial (the one with a larger expected\n",
      "is com-\n",
      "average cost) policy thereafter than the one for which\n",
      "puted. Finally, by comparing (29) with (27) and (28), we con-\n",
      "clude that\n",
      "\n",
      "in state\n",
      "\n",
      "Therefore, by combining this result with (24) and (25), we con-\n",
      "clude that\n",
      "\n",
      "(31)\n",
      "Comparing the above equation with (26), we see that (21) holds.\n",
      "We have now proven that if the ACFRL-2 critic has converged,\n",
      "then the Q-values it will supply to the actor will result in actor’s\n",
      "parameters being updated in the gradient direction.\n",
      "\n",
      "Our experimental results in the power control problem show\n",
      "that the separated exploration in ACFRL-2 provides the correct\n",
      "direction for updating all actor’s parameters at every iteration of\n",
      "ACFRL-2, which allows to use a large learning rate for the actor\n",
      "and results in a very fast convergence to a very good near-policy.\n",
      "In contrast, exploration of the full action space in ACFRL re-\n",
      "sults in very noisy updates where the correct direction for each\n",
      "parameter is chosen approximately half of the time, which re-\n",
      "quires the use of a very small learning rate for the actor and leads\n",
      "to a very slow convergence.\n",
      "\n",
      "In practice, the optimal learning strategy would be to ini-\n",
      "tialize all actor’s parameters below their optimal values and use\n",
      "ACFRL-2 while all parameters are increasing. When any one\n",
      "of the parameters will decrease, the neighborhood of optimal\n",
      "values has been reached, and ACFRL with a full Gaussian ex-\n",
      "ploration can then be used during critic’s learning if conver-\n",
      "gence to exact optimal parameter values is required. However, as\n",
      "results in Section VII show, such a switch for ﬁne tuning the re-\n",
      "\n",
      "VI. SIMULATION SETUP\n",
      "\n",
      "We used the algorithm of Foschini and Miljanic (F&M) [6]\n",
      "as a benchmark for our ACFRL-2 algorithm. In the F&M al-\n",
      "gorithm, a transmitter has a desired signal-to-interference ratio,\n",
      "which depends on the ratio of the transmitter’s power to the in-\n",
      "terference present at that time. Hence, in order to maintain a\n",
      "constant level of SIR, the transmitter raises its power when in-\n",
      "terference increases and lowers its power when interference de-\n",
      "creases. The asynchronous implementation of the F&M algo-\n",
      "rithm for multiple transmitters is known to converge geometri-\n",
      "cally fast to the unique Pareto optimal power assignment when\n",
      "the system is feasible [8]. The Pareto optimal assignment in this\n",
      "case means that no transmitter can change its power without de-\n",
      "creasing its SIR.\n",
      "\n",
      "The F&M algorithm was developed to satisfy the needs of\n",
      "voice transmissions, which require a low delay but are essen-\n",
      "tially not sensitive to transmission errors or lost data up to a cer-\n",
      "tain threshold. Data transmission, on the other hand, can accept\n",
      "some delay but have no tolerance for transmission errors or lost\n",
      "data. Since we focused on data transmissions in this paper, the\n",
      "Pareto optimality of the F&M algorithm no longer holds under\n",
      "our assumptions.\n",
      "\n",
      "However, F&M algorithm still provides a valuable bench-\n",
      "mark for our simulations. For a given arrival rate, higher trans-\n",
      "mission probability targets in the F&M algorithm correspond to\n",
      "smaller average levels of backlog. For any level of observed in-\n",
      "terference, F&M algorithm uses the smallest power necessary\n",
      "to support the required transmission probability target. There-\n",
      "fore, even for data transmissions, F&M algorithm is the optimal\n",
      "myopic algorithm (i.e., algorithm that optimizes only the im-\n",
      "mediate cost). By tuning the transmission probability target, it\n",
      "is possible to ﬁnd the best tradeoff between minimizing the av-\n",
      "erage backlog and minimizing the immediate power required to\n",
      "support this backlog.\n",
      "\n",
      "The policies considered in the ACFRL-2 algorithm extend the\n",
      "F&M algorithm by explicitly considering the backlog as a deci-\n",
      "sion variable, which these policies to trade off immediate power\n",
      "gains versus future cost reduction due to decreased backlog. Our\n",
      "simulation results demonstrate that this leads to a signiﬁcant\n",
      "cost reduction.\n",
      "\n",
      "Bambos and Kandukuri [2] have shown that the optimal\n",
      "power function is hump-shaped with respect to interference,\n",
      "with the height as well as the center of the hump steadily\n",
      "increasing with backlog. Therefore, the following rules used in\n",
      "the ACFRL-2 actor have a sufﬁcient expressive power to match\n",
      "the complexity of the optimal policy\n",
      "\n",
      ")\n",
      "\n",
      "If (backlog is SMALL) and (interference is SMALL) then\n",
      "(power is\n",
      "If (backlog is SMALL) and (interference is MEDIUM)\n",
      "then (power is\n",
      "If (backlog is SMALL) and (interference is LARGE) then\n",
      "(power is\n",
      "If (backlog is LARGE) and (interference is SMALL) then\n",
      "(power is\n",
      "\n",
      ")\n",
      "\n",
      ")\n",
      "\n",
      ")\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "\f",
      "VENGEROV et al.: FUZZY REINFORCEMENT LEARNING APPROACH\n",
      "\n",
      "775\n",
      "\n",
      "Fig. 1.\n",
      "\n",
      "Interference fuzzy labels used by the transmitters.\n",
      "\n",
      "Fig. 2. Backlog fuzzy labels used by the transmitters.\n",
      "\n",
      "Fig. 3. Cost\n",
      "nonresponsive environment.\n",
      "\n",
      "improvement by ACFRL-2 over F&M algorithm in a\n",
      "\n",
      "If (backlog is LARGE) and (interference is MEDIUM)\n",
      "then (power is\n",
      "If (backlog is LARGE) and (interference is LARGE) then\n",
      "(power is\n",
      "\n",
      "),\n",
      "\n",
      ")\n",
      "\n",
      "through\n",
      "\n",
      "where\n",
      "are the tunable parameters. The shapes of\n",
      "the input labels for interference and backlog are shown in Figs. 1\n",
      "and 2.\n",
      "\n",
      "The main difﬁculty in the considered power control problem\n",
      "is that a long wait is required for determining the beneﬁt of using\n",
      "a higher or a lower power. Because both arrivals and successful\n",
      "transmissions are stochastic, many traces are needed in order\n",
      "to distinguish the true value of a policy from random effects.\n",
      "However, as the next section shows, ACFRL-2 was able to deal\n",
      "successfully with this difﬁculty.\n",
      "\n",
      "VII. RESULTS AND DISCUSSION\n",
      "\n",
      "The following parameter\n",
      "\n",
      "settings were used in our\n",
      "\n",
      "experiments:\n",
      "\n",
      ";\n",
      "\n",
      ";\n",
      "\n",
      "(cid:127)\n",
      "(cid:127)\n",
      "(cid:127) Overﬂow Cost\n",
      "(cid:127) Power Cost Factor\n",
      "(cid:127) Transmission Noise\n",
      "(cid:127) Power gains\n",
      "(cid:127) Temporal differencing parameter in the ACFRL-2 critic,\n",
      "\n",
      ";\n",
      "\n",
      ";\n",
      "\n",
      ";\n",
      "\n",
      ";\n",
      "\n",
      ".\n",
      "\n",
      "In the ﬁrst set of experiments, we compared performance of\n",
      "the ACFRL-2 algorithm to that of the F&M algorithm in a non-\n",
      "responsive environment characterized by a random interference\n",
      "uniformly distributed in [0,100]. In order to evaluate perfor-\n",
      "mance of the transmitter using the ACFRL-2 algorithm, the op-\n",
      "timal integer-valued constant power level was ﬁrst determined.\n",
      "After that, the transmitter adopted a power control strategy de-\n",
      "scribed by the six fuzzy rules of the previous section, with pa-\n",
      "being initialized at the optimal constant\n",
      "rameters\n",
      "\n",
      "through\n",
      "\n",
      "power level found above. Then, the parameters\n",
      "were tuned using the ACFRL-2 algorithm until performance\n",
      "stopped improving. Finally, the resulting policy was tested for\n",
      "1000 trials.\n",
      "\n",
      "through\n",
      "\n",
      "The results are presented in Fig. 3, which shows the cost re-\n",
      "duction of the policy learned by ACFRL-2 over the F&M al-\n",
      "gorithm for different arrival rates. The target SIR in the F&M\n",
      "algorithm was tuned to provide the best performance while still\n",
      "keeping a stable backlog. To get a sense of the absolute num-\n",
      "bers, the costs incurred by the F&M algorithm for the six arrival\n",
      "rates shown in the ﬁgure were (9.7, 17.6, 25.8, 34.9, 45.1, 56.9),\n",
      "while the costs incurred by the ﬁnal ACFRL-2 policy were (3.5,\n",
      "8.4, 14.7, 23.4, 33.8, 47.9).\n",
      "\n",
      "We were able to simulate arrival rates only up to 0.6 in this and\n",
      "in the next set of experiments for the following reason. When the\n",
      "arrival rate and correspondingly the required transmission prob-\n",
      "ability approaches 1, the required power approaches inﬁnity, as\n",
      "can be seen from (2). Therefore, for an arrival rate sufﬁciently\n",
      "close to 1, it will be less costly for the transmitter to reduce the\n",
      "power to 0 and let the backlog overﬂow than to use a very high\n",
      "power and try to keep a stable backlog. For the current level of\n",
      ", this change in behavior occurs for ar-\n",
      "power cost factor\n",
      "rival rate equal to 0.7.\n",
      "\n",
      "In the second set of experiments we considered a more real-\n",
      "istic and a more challenging scenario of a responsive noisy en-\n",
      "vironment with varying path gains. Since the logic of the F&M\n",
      "algorithm consists of raising or lowering the transmission power\n",
      "when interference increases or decreases, we chose F&M algo-\n",
      "rithm for modeling the responsive nature of the environment.\n",
      "That is, the simulation model consisted of two transmitters, one\n",
      "using ACFRL-2 and the other using F&M, and interference ex-\n",
      "perienced by each one was described by (1), with the random\n",
      "noise\n",
      "\n",
      "being uniformly distributed in [20, 30].\n",
      "\n",
      "The power gain from (1) varied inversely proportional to the\n",
      "distance squared, with proportionality constant equal to 1. The\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "\f",
      "776\n",
      "\n",
      "IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 35, NO. 4, AUGUST 2005\n",
      "\n",
      "Fig. 4. Cost improvement by ACFRL-2 over F&M algorithm in a responsive\n",
      "environment.\n",
      "\n",
      "Fig. 5. Backlogs of F&M and ACFRL-2 algorithm for multitransmitter\n",
      "simulation.\n",
      "\n",
      "distance between transmitters was initialized at 1.5 and followed\n",
      "a random walk with an increment of 0.01 within the interval\n",
      "[1,2]. Variation in the distance was used to model the varying\n",
      "path gain phenomenon found in real wireless channels.\n",
      "\n",
      "As a benchmark, we considered a scenario where both\n",
      "transmitters were using the F&M algorithm. The experimental\n",
      "procedure consisted of ﬁrst ﬁnding the optimal common target\n",
      "SIR for both transmitters using the F&M algorithm. Perfor-\n",
      "mance of the ﬁrst transmitter was then recorded as a bench-\n",
      "mark for the ACFRL-2 algorithm. Then the ACFRL-2 algo-\n",
      "rithm was evaluated following the steps used in the ﬁrst set\n",
      "of experiments. The results are presented in Fig. 4. To get a\n",
      "sense of the absolute numbers, the costs incurred by the F&M\n",
      "algorithm were (6.1, 11.2, 17.9, 26.3, 37.2, 53.3), while the\n",
      "costs incurred by the ﬁnal ACFRL-2 policy were (4.5, 9.1,\n",
      "14.8, 22.8, 33.4, 50.9).\n",
      "\n",
      "In our third set of experiments, we considered a realistic\n",
      "scenario of nine transmitters sharing the same channel and cre-\n",
      "ating interference for each other according to (1). The random\n",
      "was once again uniformly distributed in [20, 30]. For\n",
      "noise\n",
      "symmetry, we placed all transmitters at the distance of ﬁve\n",
      "units of length from each other. The transmitters were using the\n",
      "ACFRL-2 algorithm in an online fashion to tune their transmis-\n",
      "sion policies. We stopped learning after 1000 trials and tested\n",
      "the resulting policies by recording the average power level and\n",
      "the average backlog among the nine transmitters. To evaluate\n",
      "these results, we considered the case when all nine transmitters\n",
      "were using the F&M algorithm with the target SIR being tuned\n",
      "so that the average power among the transmitters equals to\n",
      "that in the ﬁnal ACFRL-2 policy. After that, we compared the\n",
      "average backlogs of the transmitters using the F&M algorithm\n",
      "and those using the policies learned by ACFRL-2. The results\n",
      "are presented in Fig. 5 for arrival rates 0.1 to 0.7.\n",
      "\n",
      "The shape of the policy learned by ACFRL-2 in the ﬁrst\n",
      "experiment is exactly as predicted by Bambos and Kandukuri\n",
      "[2] for this setup. That is, for low values of backlog the trans-\n",
      "\n",
      "mitter uses positive power only for low levels of interference\n",
      "and goes into a backoff mode for medium and high interfer-\n",
      "ence. Rather than ﬁghting the interference with a high power\n",
      "level, the transmitter buffers the arriving packets and waits for\n",
      "a time slot with a low interference to transmit. However, this\n",
      "behavior is dangerous for high levels of backlog because the\n",
      "buffer can overﬂow, and ACFRL-2 learns to go only into a soft\n",
      "backoff mode for high levels of interference when backlog is\n",
      "large.\n",
      "\n",
      "As arrival rate increases, the problem faced by the transmitter\n",
      "becomes more challenging. There is less freedom in using small\n",
      "power and buffering the arriving packets for high levels of inter-\n",
      "ference because of the danger that the buffer can overﬂow. As a\n",
      "result, the optimal policy approaches the one used by the F&M\n",
      "algorithm—always maintaining the same transmission proba-\n",
      "bility. This explains the decrease in the beneﬁt of ACFRL-2\n",
      "shown in Figs. 3 and 4 for increasing arrival rates.\n",
      "\n",
      "Fig. 5 shows that ACFRL-2 is able to learn policies that\n",
      "reduce backlog by more than a factor of 2 for low arrival rates\n",
      "in comparison with the F&M algorithm. For the high arrival\n",
      "rate of 0.7, we found that F&M algorithm simply cannot keep\n",
      "the backlog stable when it attempts to transmit at the same\n",
      "power level as the one learned by the ACFRL-2 algorithm.\n",
      "Thus, ACFRL-2 algorithm can both increase the maximal net-\n",
      "work throughput by keeping the backlog stable at high arrival\n",
      "rates and increase the network efﬁciency by decreasing the\n",
      "competition between transmitters.\n",
      "\n",
      "In order to understand the reasons for such a drastic perfor-\n",
      "mance improvement of ACFRL-2 over F&M, we considered a\n",
      "simpliﬁed problem of only three transmitters sharing the wire-\n",
      "less channel. Also, after observing that the ACFRL-2 algorithm\n",
      "learns the hump-shaped backoff policy, we simpliﬁed the work\n",
      "of the actor by explicitly coding this knowledge into the struc-\n",
      "ture of the fuzzy rulebase governing the power selection in each\n",
      "transmitter. That is, we ﬁxed at 0 the parameters\n",
      "of each rulebase.\n",
      "\n",
      "through\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "\f",
      "TABLE II\n",
      "COMPARISON OF AVERAGE BACKLOG OF THE ACFRL-2 POLICY WITH\n",
      "THE BENCHMARK POLICIES FOR HIGH NOISE LEVEL\n",
      "\n",
      "VENGEROV et al.: FUZZY REINFORCEMENT LEARNING APPROACH\n",
      "\n",
      "777\n",
      "\n",
      "TABLE I\n",
      "COMPARISON OF AVERAGE BACKLOG OF THE ACFRL-2 POLICY WITH\n",
      "THE BENCHMARK POLICIES FOR LOW NOISE LEVEL\n",
      "\n",
      "value, implying that each transmitter goes into a backoff mode\n",
      "when interference surpasses a certain threshold.\n",
      "\n",
      "The above observation suggested comparing the ACFRL-2\n",
      "policy against the policy where only the transmitter with the\n",
      "highest backlog is allowed to transmit in each time slot. This\n",
      "explicit turn-taking policy belongs to a class of efﬁcient but not\n",
      "scalable centralized control policies with a single entity making\n",
      "fully informed decisions. Therefore, in our small-scale simula-\n",
      "tion we expected this policy to outperform ACFRL-2.\n",
      "\n",
      "We tested this hypothesis by applying the centralized policy\n",
      "to the fuzzy rulebased transmitters and following a similar com-\n",
      "parison process to the one used for the F&M policy. That is,\n",
      "we adjusted the tunable coefﬁcients in the fuzzy rulebases until\n",
      "the average power used by three transmitters matched the power\n",
      "used by the transmitters tuned with ACFRL-2. The results are\n",
      "presented on the last line of Tables I and II. As these tables show,\n",
      "the transmitters using ACFRL-2 to tune their policies in a dis-\n",
      "tributed fashion still outperformed the centralized policy. From\n",
      "this we can conclude that ACFRL-2 allows the transmitters to\n",
      "learn an optimal balance between transmitting simultaneously\n",
      "and taking turns for transmission.\n",
      "\n",
      "VIII. CONCLUSION\n",
      "\n",
      "In this paper we presented a new fuzzy reinforcement learning\n",
      "algorithm, ACFRL-2, for optimal decision making in highly sto-\n",
      "chastic problems with long renewal periods and long-lasting\n",
      "memory of actions that have very large state and action spaces.\n",
      "We presented a convergence proof for ACFRL-2 in the context\n",
      "of the power control problem, which relied on the “ordered ac-\n",
      "tion space” property of this problem. This property arose be-\n",
      "cause the real world analog of our discretized model has a con-\n",
      "tinuous action space. Therefore, we can conclude that ACFRL-2\n",
      "algorithm has a potential of solving many previously unsolved\n",
      "real world problems that have very large state spaces and very\n",
      "large or continuous action spaces.\n",
      "\n",
      "As a test case, we have applied ACFRL-2 algorithms to the\n",
      "wireless power control problem, which has continuous state and\n",
      "action spaces. The benchmark in our experiments was the stan-\n",
      "dard algorithm of Foschini and Miljanic [6]. In a nonresponsive\n",
      "environment characterized by a random interference, the poli-\n",
      "cies learned by the ACFRL-2 algorithm improved the cost of\n",
      "the F&M algorithm by 175% for low arrival rates and 18% for\n",
      "high arrival rates.\n",
      "\n",
      "In a more challenging and a more realistic scenario of a\n",
      "responsive environment with varying path gains, the policies\n",
      "learned by the ACFRL-2 algorithm improved the cost of the\n",
      "F&M algorithm by 35% for low arrival rates and 5% for high\n",
      "arrival rates. The decreasing utility of the ACFRL-2 algorithm\n",
      "for high arrival rates is due to the fact that as environment\n",
      "the\n",
      "becomes more antagonistic,\n",
      "algorithm can potentially learn becomes less effective.\n",
      "\n",
      "the backoff behavior that\n",
      "\n",
      "When ran a realistic simulation with nine transmitters sharing\n",
      "the same channel and causing interference to each other. We\n",
      "recorded the practical performance measures of average trans-\n",
      "mission delay and the maximal throughput. We found that for\n",
      "low arrival rates the ACFRL-2 algorithm reduced the average\n",
      "\n",
      "Fig. 6. Power levels over time of three transmitters using a policy learned by\n",
      "ACFRL-2.\n",
      "\n",
      "We then used the same experimental procedure as above for\n",
      "comparing the ACFRL-2 algorithm with the F&M algorithm.\n",
      "The average backlogs of the two policies are presented in Ta-\n",
      "bles I and II. These results show that ACFRL-2 signiﬁcantly\n",
      "decreases the average system backlog in comparison with the\n",
      "F&M algorithm for the case of low external noise level. This\n",
      "improvement reaches a new level of importance for the case of\n",
      "high external noise level, where ACFRL-2 increases the max-\n",
      "imum system throughput by keeping the backlog stable where\n",
      "the F&M policy leads to a backlog overﬂow.\n",
      "\n",
      "We then plotted the backlogs of all the transmitters in a\n",
      "channel over time. Fig. 6 shows this plot for the ﬁnal policy\n",
      "learned by ACFRL-2. As can be seen from that graph, the\n",
      "transmitters learn to implicitly coordinate their actions and\n",
      "take turns during the transmission. This behavior can also be\n",
      "inferred from the ﬁnal values of the rulebase parameters\n",
      ",\n",
      "attained a large negative\n",
      "and\n",
      "\n",
      ". In all the learning scenarios,\n",
      "\n",
      ",\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "\f",
      "778\n",
      "\n",
      "IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 35, NO. 4, AUGUST 2005\n",
      "\n",
      "delay by more than a factor of 2 in comparison with the F&M\n",
      "algorithm. Moreover, for high arrival rates the F&M algorithm\n",
      "simply could not keep a stable backlog while the ACFRL-2 al-\n",
      "gorithm was able to maintain a ﬁnite backlog thereby increasing\n",
      "the maximal network throughput.\n",
      "\n",
      "Analysis of this performance improvement of ACFRL-2 over\n",
      "F&M revealed that the transmitters learn to implicitly coordi-\n",
      "nate their actions and take turns during the transmission. After\n",
      "comparing ACFRL-2 with an explicit turn-taking policy based\n",
      "on centralized control, we found that ACFRL-2 still performed\n",
      "better. This leads to a conclusion that ACFRL-2 allows the trans-\n",
      "mitters to learn an optimal balance between transmitting simul-\n",
      "taneously and taking turns for transmission.\n",
      "\n",
      "REFERENCES\n",
      "\n",
      "[1] N. Bambos, “Toward power-sensitive network architectures in wireless\n",
      "communications: Concepts, issues and design aspects,” IEEE Pers.\n",
      "Commun. Mag., vol. 5, no. 3, pp. 50–59, Jun. 1998.\n",
      "\n",
      "[2] N. Bambos and S. Kandukuri, “Power controlled multiple access\n",
      "(PCMA) in wireless communication networks,” in Proc. IEEE Conf.\n",
      "Computer Communications (INFOCOM), 2000, pp. 386–395.\n",
      "\n",
      "[3] H. R. Berenji and D. Vengerov, “On convergence of fuzzy reinforce-\n",
      "ment learning,” in Proc. 10th IEEE Int. Conf. Fuzzy Systems, 2001, pp.\n",
      "618–621.\n",
      "\n",
      "[4]\n",
      "\n",
      ", “A convergent actor critic based fuzzy reinforcement learning\n",
      "algorithm with application to power management of wireless trans-\n",
      "mitters,” IEEE Trans. Fuzzy Syst., vol. 11, no. 4, pp. 478–485, Aug.\n",
      "2003.\n",
      "\n",
      "[5] D. Bertsekas and J. Tsitsiklis, Neuro-Dynamic Programming. New\n",
      "\n",
      "York: Atheneum, 1996.\n",
      "\n",
      "[6] G. J. Foschini and Z. Miljanic, “A simple distributed autonomous power\n",
      "control algorithm and its convergence,” IEEE Trans. Vehic. Technol., vol.\n",
      "42, no. 4, pp. 641–646, Nov. 1993.\n",
      "\n",
      "[7] D. J. Goodman and N. B. Mandayam, “Power control for wireless data,”\n",
      "\n",
      "IEEE Pers. Commun., vol. 7, no. 2, pp. 48–54, Apr. 2000.\n",
      "\n",
      "[8] D. Mitra, “An asynchronous distributed algorithm for power control\n",
      "in cellular radio systems,” in Proc. 4th WINLAB Workshop, 1993, pp.\n",
      "249–257.\n",
      "\n",
      "[9] J. Monks, V. Bharghavan, and W. Hwu, “A power controlled multiple\n",
      "access protocol for wireless packet networks,” in Proc. IEEE Conf. Com-\n",
      "puter Communications (INFOCOM), vol. 1, 2001, pp. 1–11.\n",
      "\n",
      "[10] J. Oh, T. Olsen, and K. Wasserman, “Distributed power control and\n",
      "spreading gain allocation in CDMA data networks,” in Proc. IEEE Conf.\n",
      "Computer Communications (INFOCOM), 2000, pp. 379–385.\n",
      "\n",
      "[11] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduc-\n",
      "\n",
      "tion. Cambridge, MA: MIT Press, 1998.\n",
      "\n",
      "[12] V. R. Konda and J. N. Tsitsiklis, “Actor-critic algorithms,” Adv. Neural\n",
      "\n",
      "Inf. Process. Syst., vol. 12, pp. 1008–1014, 1999.\n",
      "\n",
      "[13] R. S. Sutton and A. G. Barto, “Toward a modern theory of adaptive net-\n",
      "works: Expectation and prediction,” Psychol. Rev., vol. 88, pp. 135–170,\n",
      "1981.\n",
      "\n",
      "[14] J. N. Tsitsiklis and B. Van Roy, “Average cost temporal-difference\n",
      "\n",
      "learning,” Automatica, vol. 35, no. 11, pp. 1799–1808, 1999.\n",
      "\n",
      "David Vengerov was born in Moscow, Russia, in\n",
      "1976. He received the B.S. degree in mathematics\n",
      "and the M.S. degree in electrical engineering and\n",
      "computer science from the Massachusetts Institute of\n",
      "Technology, Boston, in 1997 and 1998, respectively,\n",
      "the M.S. degree in engineering economic systems\n",
      "and operations research and the Ph.D. degree in\n",
      "management science and engineering from Stan-\n",
      "ford University, Stanford, CA, in 2000 and 2004,\n",
      "respectively.\n",
      "\n",
      "He joined Sun Microsystems Laboratories, Sunny-\n",
      "vale, CA, in 2003, where he is currently developing adaptive algorithms based on\n",
      "distributed intelligence and agent-based systems for domains such as for utility-\n",
      "based scheduling, dynamic data migration in hierarchical storage systems, load\n",
      "balancing, dynamic resource allocation in distributed computer systems, etc.\n",
      "\n",
      "Nicholas Bambos received the Ph.D. degree in elec-\n",
      "trical engineering from the University of California,\n",
      "Berkeley, in 1989.\n",
      "\n",
      "He is currently a Professor at Stanford University,\n",
      "Stanford, CA, holding a joint appointment in the De-\n",
      "partment of Electrical Engineering and the Depart-\n",
      "ment of Management Science. His current research\n",
      "interests include high-performance network architec-\n",
      "tures, wireless networks and power control, queueing\n",
      "modeling and congestion control, etc.\n",
      "\n",
      "Dr. Bambos received the NSF Young Investigator\n",
      "Award, has been the Cisco Systems Chair at Stanford, and has received the IBM\n",
      "Faculty Award.\n",
      "\n",
      "Hamid R. Berenji (F’02) received the B.S. degree\n",
      "from Iran University of Science and Technology,\n",
      "Tehran, in 1979, and the M.S. and Ph.D. degrees\n",
      "in systems engineering from the University of\n",
      "Southern California, Los Angeles, in 1980 and 1986,\n",
      "respectively.\n",
      "\n",
      "He is currently a Fellow of the Berkeley Initiative\n",
      "on Soft Computing (BISC) at the EECS Department,\n",
      "University of California, Berkeley. He is a Senior\n",
      "Scientist with the Intelligent Inference Systems Cor-\n",
      "poration, Mountain View, CA, and has many years\n",
      "of experience in performing Research and Development at the Computational\n",
      "Sciences Division of NASA Ames Research Center, Moffett Field, CA. In a\n",
      "joint project between the NASA Ames Research Center and the NASA Johnson\n",
      "Space Center, he and his team developed a new controller for the Shuttle\n",
      "Training Aircraft (STA) that signiﬁcantly improved its accuracy as tested in\n",
      "the ground hardware facility of NASA, Ellington Field, TX. He originated and\n",
      "extended the theory of generalized reinforcement learning. He has published\n",
      "about 100 technical publications including several book chapters, journal\n",
      "papers, and refereed conference proceeding papers. He was an Area Editor for\n",
      "the Journal of Fuzzy Sets and Systems.\n",
      "\n",
      "Dr. Berenji is the winner of the 1999 NASA Space Act Award and a winner\n",
      "of the NASA Ames Director’s Discretionary Fund. He was the Program\n",
      "Co-chairman of the 1993 IEEE Conference on Neural Networks and a Program\n",
      "Co-chairman of the 1994 IEEE Conference on Fuzzy Systems. He has served\n",
      "as an Associate Editor for the IEEE TRANSACTIONS ON NEURAL NETWORKS\n",
      "and the IEEE TRANSACTIONS ON FUZZY SYSTEMS.\n",
      "\n",
      "Authorized licensed use limited to: Universitaet Mannheim. Downloaded on May 09,2020 at 12:53:27 UTC from IEEE Xplore.  Restrictions apply. \n",
      "\n",
      "\f",
      "\n",
      "Wall time: 2 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "if __name__ == '__main__':\n",
    "    pdfConverter = PdfConverter(file_path='example2.pdf')\n",
    "    print(pdfConverter.convert_pdf_to_txt())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "MaSTerClass\n",
      "FukudaÕsapproachtosixclassesofbiomedicalentities:geneorpro-\n",
      "tein,geneorproteinpart,chemical,chemicalpart,sourceandothers.\n",
      "\n",
      "ThemainprobleminsuchapproachesisthattermclassiÞcationrules\n",
      "\n",
      "areoftenobscureandimpreciseduetoloosenamingconventions.\n",
      "InordertocopeefÞcientlywiththecomplexityofknowledge\n",
      "neededtoperformreliableclassiÞcation,manyapproachesresort\n",
      "\n",
      "tomachinelearning(ML)techniquestodetectfeaturesthatchar-\n",
      "\n",
      "acterizespeciÞcclasses.Currently,theMLtermclassiÞcation\n",
      "\n",
      "methodsexploitlittleornobiomedicalknowledgeforguidedlearn-\n",
      "\n",
      "ing.Usually,general-purposeMLalgorithmsareappliedtoshallow\n",
      "\n",
      "representationoftext(Nedellec,2002).Forinstance,Stapley\n",
      "etal\n",
      ".\n",
      "(2002)usedasupportvectormachine(SVM)approachwitha\n",
      "\n",
      "non-structuredrepresentationoftexttoclassifygenenames(rep-\n",
      "\n",
      "resentedasvectorsofcontextualfeatures,deÞnedassinglewords\n",
      "\n",
      "co-occurringinthesameabstract)withrespecttotheirsubcellular\n",
      "\n",
      "location.Recently,therehavebeenanumberofotherapplicationsof\n",
      "\n",
      "SVMsforclassiÞcationofbiomedicalterms(Kazama\n",
      "etal\n",
      ".,2002;\n",
      "Lee\n",
      "etal\n",
      ".,2004;CollierandTakeuchi,2004).Theseapproachesdif-\n",
      "ferfromthoseofStapley\n",
      "etal\n",
      ".(2002)withrespecttothefeatures\n",
      "usedwhichlargelyresemblethoseproposedbyFukuda\n",
      "etal\n",
      ".(1998).\n",
      "Alternatively,probabilisticmethodssuchasnaiveBayesclassiÞca-\n",
      "\n",
      "tion(Hatzivassiloglou\n",
      "etal\n",
      ".,2001;Nobata\n",
      "etal\n",
      ".,2000)andhidden\n",
      "Markovmodels(Collier\n",
      "etal\n",
      ".,2001)havebeenused.\n",
      "Allmentionedmethodsrequirelargeamountsoftrainingdataand\n",
      "signiÞcanttrainingtimetopreventoverÞtting.Namely,theyare\n",
      "\n",
      "optimizedtoÞtthetrainingdata,whichmaynotbeidealapprox-\n",
      "\n",
      "imationoftherealdata.Thus,suchalgorithmsrequirelargetraining\n",
      "\n",
      "setsandneedtobeperiodicallyretrainedupontheadventofnewdata.\n",
      "\n",
      "Theyalsounderperformforminorityclassesduetothedatasparsity\n",
      "\n",
      "problem.Furthermore,theyexplicitlydifferentiatebetweenthetrain-\n",
      "\n",
      "ingphase(inwhichclassiÞcationrulesarelearnt)andtheapplication\n",
      "\n",
      "phase(inwhichthelearntrulesareapplied).However,satisfact-\n",
      "\n",
      "oryrulescannotalwaysbeproduced(e.g.duetoweakcorrelation\n",
      "\n",
      "betweentermfeaturesandtheirclasses).\n",
      "InthispaperwesuggestanalternativeMLapproach.Case-based\n",
      "reasoning(CBR)isparticularlysuitablefortheproblemoftermclas-\n",
      "\n",
      "siÞcationinbiomedicine,becauseitispragmaticandrobustenough\n",
      "\n",
      "todealwiththecomplexityofbothnaturallanguageandthebiomed-\n",
      "\n",
      "icaldomainasexplainedinthefollowingsectionwhichoutlinesthe\n",
      "\n",
      "basicprinciplesofthismethodology.\n",
      "2METHODOLOGY\n",
      "CBRisbasedonrememberingspeciÞcexperiencesthatmaybeusefulforthe\n",
      "problem(case)beingsolved.Itmaybeviewedasamultistagecycleinvolving\n",
      "\n",
      "thefourÔ\n",
      "re-\n",
      "Õ(Aamodt,1995):(1)\n",
      "retrieve\n",
      "themostsimilarcase,(2)\n",
      "reuse\n",
      "the\n",
      "casetosolvethenewproblem,(3)\n",
      "revise\n",
      "thesuggestedsolutionand(4)\n",
      "retain\n",
      "theusefulinformationobtainedduringproblemsolving.Therefore,newprob-\n",
      "\n",
      "lemsaresolvedbyadaptingsolutionsthatprovidedsatisfactoryresultsfor\n",
      "\n",
      "similarproblems,thusavoidingtheneedforanexplicitmodeloftheproblem\n",
      "\n",
      "domain(WatsonandMarir,1994).Instead,onlyfeaturesrelevantinthecon-\n",
      "\n",
      "textofthecurrentproblemneedtobeidentiÞed.Therefore,CBRmakesuse\n",
      "\n",
      "of\n",
      "speciÞc\n",
      "(asopposedtogeneralized)knowledgeinbothproblemsolving\n",
      "andlearning(Kolodner,1993).SpeciÞcinformationaboutthepastexperi-\n",
      "\n",
      "encesisregardedas\n",
      "knowledge\n",
      ",unlikeinrule-basedormodel-basedsystems,\n",
      "whereitistreatedas\n",
      "data\n",
      ".Inthismanner,CBRtacklesthemainissuesin\n",
      "otherMLsystems,suchasthelackofrobustnessandßexibility,conÞne-\n",
      "\n",
      "menttonarrowproblemdomainsanddifÞcultdevelopmentandmaintenance\n",
      "\n",
      "(Aamodt,1995).\n",
      "MemoryformsabasisforthelearningabilityofCBRsystems(Watson\n",
      "andMarir,1994).Nevertheless,suchatrivialformoflearningstillsupports\n",
      "generalizationandabstractionimplicitlythroughtheuseofsimilarity\n",
      "(Aamodt,1995).Therefore,aCBRsystemiscapableoflearningwithout\n",
      "\n",
      "explicitlygeneralizingspeciÞccasesintoformulas,rulesorothersymbolic\n",
      "\n",
      "representations(Globig\n",
      "etal\n",
      ".,1997).Suchalazyordemand-drivenapproach\n",
      "hasthefollowingadvantages(Aha,1998;Leake,1996):easierknowledge\n",
      "\n",
      "acquisition,reducedproblemsolvingpredisposition,incrementallearning\n",
      "\n",
      "andimproveduseracceptanceduetoexplanationbasedonprecedents.\n",
      "ThegeneraladvantagesofCBRareparticularlyemphasizedinthefamily\n",
      "ofbiomedicalsciencesbecauseofthehomologousnatureofbiologicalsys-\n",
      "\n",
      "temsrootedinevolution(JurisicaandGlasgow,2004).Therefore,biomedical\n",
      "\n",
      "expertsthemselvesoftenuseanalogicalreasoningtoplanandconductexper-\n",
      "\n",
      "imentsexploringsimilaritiesbetweennewandknownsystems.Furthermore,\n",
      "\n",
      "biomedicalÞeldisoverwhelmedbydatabutoftenlacksexactandcomplete\n",
      "\n",
      "theoriesthatcouldinterpretsuchamountsofdatacorrectlyandefÞciently.\n",
      "\n",
      "Forexample,duetohugeamountsofdata,manyunknowns,incomplete\n",
      "\n",
      "theoriesandextremelydynamicnatureofmolecularbiology,reasoningin\n",
      "\n",
      "thisdomainisoftenbasedonexperienceasopposedtogeneralknowledge.\n",
      "\n",
      "CBRhasbeensuccessfullyappliedinmolecularbiologytosolveavariety\n",
      "\n",
      "ofproblems,e.g.proteincrystallization,genomicsequenceanalysis,protein\n",
      "\n",
      "structuredetermination,etc.\n",
      "Similarly,Schmidt\n",
      "etal\n",
      ".(2001)emphasizetheappropriatenessofCBR\n",
      "formedicaldomainusinganargumentthattheknowledgeofmedicalexperts\n",
      "\n",
      "isÔamixtureoftextbookknowledgeandexperienceÕ.Thetextbookknow-\n",
      "\n",
      "ledgecanberepresentedbyrulesorothermodels,whiletheexperiencecan\n",
      "\n",
      "berepresentedbycases.Moreover,medicalcasesareprofessionallydocu-\n",
      "\n",
      "mentedresultinginaninvaluablerepositoryofinformation,whereCBRcan\n",
      "\n",
      "beusedasÔanengineforintelligenttextprocessingandretrieval,datamining\n",
      "\n",
      "andprojectivereasoningÕinordertofullyexploitavailableinformationespe-\n",
      "\n",
      "ciallyintheageofelectronicpatientrecords(MacuraandMacura,1997).\n",
      "\n",
      "Furthermore,thetypicaldecisionmakingprocessofamedicalpractitioner\n",
      "\n",
      "involvesreasoningwithcases,whichestablishesmedicineasaninteraction\n",
      "\n",
      "ofresearchandpractice,whereclinicalpracticeischaracterizedbyacollec-\n",
      "\n",
      "tionofaccumulatedcases.CBRanditslearningstrategymirrorthelearning\n",
      "\n",
      "processofamedicalpractitionerwhenfacedwithdifferentcases(patients,\n",
      "\n",
      "symptoms,diseasesandtreatments).Hence,cognitiveadequatenessand\n",
      "\n",
      "explicitrepresentationofexperiencemakeCBRanaturalMLapproach\n",
      "\n",
      "inmedicine(Gierl\n",
      "etal\n",
      ".,1998).Thisfacthasbeenrestatedbynumerous\n",
      "medicalapplicationsincludingdiagnosis,classiÞcation,planning,prognosis,\n",
      "\n",
      "tutoring,etc.\n",
      "InviewofourspeciÞcproblemofclassifyingbiomedicalterms,CBRcan\n",
      "readilyutilizethelargebodyofbiomedicaltextsasthetrainingdatawithout\n",
      "\n",
      "theneedtomaptermfeaturestothecorrespondingclasses,apriori.Instead,\n",
      "\n",
      "generalization(orlearning)isperformedondemandbasedonthecurrently\n",
      "\n",
      "availabledataandwithrespecttoaparticulartermbeingclassiÞed.Thishelps\n",
      "\n",
      "toreduceoverÞtting,whichinotherMLapproachesstemsfromanattemptto\n",
      "\n",
      "generalizeinadvancesoastoÞtmostoftheavailabletrainingdata.Moreover,\n",
      "\n",
      "byautomaticallyadaptingtothedataavailableatthemomentofclassiÞcation\n",
      "\n",
      "andnottraining,theneedforretrainingisavoidedinCBR.Theseproperties\n",
      "\n",
      "particularlysuitthedynamicnatureofthebiomedicaldomain(newdata\n",
      "\n",
      "becomeavailabledaily)andthedifÞcultyingeneralizingtermpropertiesinto\n",
      "\n",
      "correspondingclasses(duetoloosenamingconventionsandthevariability\n",
      "\n",
      "ofnaturallanguages).\n",
      "HavingchosenCBRasamethodologyforclassiÞcationofbiomedical\n",
      "terms,thenextstepistodecidehowtoutilizeitforthisproblem.First,\n",
      "\n",
      "notethatthereisalargeamountofelectronicallyavailablebiomedical\n",
      "\n",
      "documentsdescribingspeciÞcdiscoveriesandanumberofknowledgerepos-\n",
      "\n",
      "itoriesdescribinggeneralbiomedicalknowledge.Thebiomedicalknowledge\n",
      "\n",
      "repositories,althoughtypicallyincomplete,stillcontainlargevolumesof\n",
      "\n",
      "informationinastructuredform.Ontheotherside,scientiÞcdocuments\n",
      "\n",
      "containcomprehensiveup-to-dateinformationstructuredbythenaturallan-\n",
      "\n",
      "guagerules.Ourintentionwastouseacorpusofbiomedicaltexts(inwhich\n",
      "\n",
      "knowntermsareclassiÞedwithinabiomedicalontology)asacollectionof\n",
      "\n",
      "classiÞcationexperiencesandperformclassiÞcationofnewtermsbymaking\n",
      "\n",
      "analogiesontheßy.Theroleofanontologyinthiscontextistoprovidea\n",
      "\n",
      "classiÞcationscheme,aidsemanticinterpretationofdomain-speciÞctextand\n",
      "2749\n",
      "Downloaded from https://academic.oup.com/bioinformatics/article-abstract/21/11/2748/294681 by Universitätsbibliothek Mannheim user on 09 May 2020\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import PyPDF4\n",
    "import re\n",
    "import io\n",
    "\n",
    "pdfFileObj = open(r'bti338.pdf', 'rb')\n",
    "pdfReader = PyPDF4.PdfFileReader(pdfFileObj)\n",
    "pageObj = pdfReader.getPage(1)\n",
    "pages_text = pageObj.extractText()\n",
    "\n",
    "for line in pages_text.split('\\n'):\n",
    "    #if re.match(r\"^PDF\", line):\n",
    "    print(line)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
